Straight Walk Algorithm Modification for Point location in a Trianglulation

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

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Straight Walk Algorithm Modification for Point location in a Trianglulation

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Straight Walk Algorithm Modification for Point location in a Trianglulation

Popis výsledku anglicky

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.

Druh

O - Ostatní výsledky

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F09%2F0097" target="_blank" >GA201/09/0097: Triangularizované modely pro haptiku a virtuální realitu</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2009

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ů