Technical reports

A robust efficient algorithm for point location in triangulations

Peter J.C. Brown, Christopher T. Faigle

February 1997, 16 pages

This report was written in February 1997 but not formally submitted to the Technical Report series until September 2008.

DOI: 10.48456/tr-728

Abstract

This paper presents a robust alternative to previous approaches to the problem of point location in triangulations represented using the quadedge data structure. We generalise the reasons for the failure of an earlier routine to terminate when applied to certain non-Delaunay triangulations. This leads to our new deterministic algorithm which we prove is guaranteed to terminate. We also present a novel heuristic for choosing a starting edge for point location queries and show that this greatly enhances the efficiency of point location for the general case.

Full text

PDF (0.3 MB)

BibTeX record

@TechReport{UCAM-CL-TR-728,
  author =	 {Brown, Peter J.C. and Faigle, Christopher T.},
  title = 	 {{A robust efficient algorithm for point location in
         	   triangulations}},
  year = 	 1997,
  month = 	 feb,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-728.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-728},
  number = 	 {UCAM-CL-TR-728}
}