Straight Walk Algorithm Modification for Point location in a Trianglulation
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F09%3A00502676" target="_blank" >RIV/49777513:23520/09:00502676 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Straight Walk Algorithm Modification for Point location in a Trianglulation
Original language description
Finding an element in a mesh which contains a query point is a very frequent task in computational geometry. The best known algorithms use additional data structures and achieve O(log n) complexity per point query, but using of additional data structuresbrings some disadvantages. Generally walking algorithms are suboptimal because they do not achieve the logarithmic per point complexity. Despite this problem walking algorithms are very popular because they do not require any additional memory and theirimplementation is relatively simpler than the logarithmic complexity solutions. This paper brings overview of algorithms from all three known planar walking strategies (Visibility walk, Straight walk and Orthogonal walk). Our goal is to introduce algorithms of mentioned techniques and compare each of them with each other.
Czech name
—
Czech description
—
Classification
Type
O - Miscellaneous
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA201%2F09%2F0097" target="_blank" >GA201/09/0097: Triangulated models in service of haptic and virtual reality</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2009
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů