A new visibility walk algorithm for point location in planar triangulation

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

A new visibility walk algorithm for point location in planar triangulation

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

A new visibility walk algorithm for point location in planar triangulation

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP202%2F10%2F1435" target="_blank" >GAP202/10/1435: Analýza a vizualizace proteinových struktur</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2012

Kód důvěrnosti údajů

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

Název statě ve sborníku

Advances in Visual Computing, 8th International Symposium, ISVC 2012

ISBN

978-3-642-33191-6

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

10

Strana od-do

736-745

Název nakladatele

Springer Verlag

Místo vydání

Heidelberg, Berlin

Místo konání akce

Kréta, Rethymnon

Datum konání akce

16. 7. 2012

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—