A new visibility walk algorithm for point location in planar triangulation

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F12%3A43915733" target="_blank" >RIV/49777513:23520/12:43915733 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-642-33191-6_73" target="_blank" >http://dx.doi.org/10.1007/978-3-642-33191-6_73</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-33191-6_73" target="_blank" >10.1007/978-3-642-33191-6_73</a>

Result language
angličtina
Original language name
A new visibility walk algorithm for point location in planar triangulation
Original language description
Finding which triangle in a planar triangle mesh contains a query point is one of the most frequent tasks in computational geometry. Usually, a large number of point locations has to be performed, and so there is a need for fast algorithms resistant to changes in triangulation and having minimal additional memory requirements. The so-called walking algorithms offer low complexity, easy implementation and negligible additional memory requirements, which makes them suitable for such applications. In thispaper, we propose a walking algorithm which significantly improves the current barycentric approach and propose how to effectively combine this algorithm with a suitable hierarchical structure in order to improve its computational complexity. The hierarchical data structure used in our solution is easy to implement and requires low additional memory while providing a significant acceleration thanks to the logarithmic computational complexity of the search process.
Czech name
—
Czech description
—

Project
<a href="/en/project/GAP202%2F10%2F1435" target="_blank" >GAP202/10/1435: Analysis and Visualization of Protein Structures</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Advances in Visual Computing, 8th International Symposium, ISVC 2012
ISBN
978-3-642-33191-6
ISSN
0302-9743
e-ISSN
—
Number of pages
10
Pages from-to
736-745
Publisher name
Springer Verlag
Place of publication
Heidelberg, Berlin
Event location
Kréta, Rethymnon
Event date
Jul 16, 2012
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)