Přejít k obsahu


A small improvement in the walking algorithm for point location in a triangulation

Citace: [] KOLINGEROVÁ, I. A small improvement in the walking algorithm for point location in a triangulation . In 22nd European workshop on computational geometry. Athens: National & Kapodistrian University of Athens, University of Ioannina, University of Crete, 2006. s. 221-224.
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: A small improvement in the walking algorithm for point location in a triangulation
Rok vydání: 2006
Místo konání: Athens
Název zdroje: National & Kapodistrian University of Athens, University of Ioannina, University of Crete
Autoři: Ivana Kolingerová
Abstrakt CZ: Článek ukazuje jednoduchou techniku, která šetří část testů hran v algoritmu procházky pro lokaci bodu. Algoritmus procházky nedosahuje logaritmické složitosti na bod, kterou mají metody užívající lokační datové struktury, ale nepotřebuje pomocné datové struktury a je implementně jednoduché, a proto v praxi populární.
Abstrakt EN: The paper shows a simple technique which saves some edge test in the walking algorithm for point location. The walking technique does not achieve the logarithmic per point complexity of the location-data-structure-based methods but does not need any auxiliary data structure and is very simple to implement, therefore, it is very popular in practice.
Klíčová slova

Zpět

Patička