Algorithm to locate points in a delaunay triangulation

Hui Zhao, Marwan Bikdash

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

We present an algorithm to locate quickly the positions of several points within triangles of a given Delaunay triangulation in the plane. The proposed algorithm locates the query point simply by determining the closest node in the triangulation then by testing elements connected to that node within a small often pre-computable Graph-Theoretic Radius (GTR). A bound on the graph-theoretic radius containing the query point is derived and its relation is characterized analytically in terms of the sharpness of the elements angles. Empirical results show that this procedure is more efficient in practice than existing algorithms.

Original languageEnglish
Title of host publicationProceedings of the 38th Southeastern Symposium on System Theory
Pages211-215
Number of pages5
StatePublished - 2006
Externally publishedYes
Event38th Southeastern Symposium on System Theory - Cookeville, TN, United States
Duration: Mar 5 2006Mar 7 2006

Publication series

NameProceedings of the Annual Southeastern Symposium on System Theory
Volume2006

Conference

Conference38th Southeastern Symposium on System Theory
Country/TerritoryUnited States
CityCookeville, TN
Period03/5/0603/7/06

Fingerprint

Dive into the research topics of 'Algorithm to locate points in a delaunay triangulation'. Together they form a unique fingerprint.

Cite this