%0 Report %1 Brown1997Robust %A Brown, Peter J. C. %A Faigle, Christopher T. %B Technical Report %D 1997 %K 65d18-computer-graphics-computational-geometry 65n50-pdes-bvps-mesh-generation-and-refinement %N UCAM-CL-TR-728 %T A Robust Efficient Algorithm for Point Location in Triangulations %U https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-728.html %X 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.

@techreport{Brown1997Robust, 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.}}, added-at = {2019-03-01T00:11:50.000+0100}, author = {Brown, Peter J. C. and Faigle, Christopher T.}, biburl = {https://www.bibsonomy.org/bibtex/23ae044305ed27cf6a0e894bddeb8314b/gdmcbain}, citeulike-article-id = {14649058}, citeulike-attachment-1 = {brown_97_robust.pdf; /pdf/user/gdmcbain/article/14649058/1147037/brown_97_robust.pdf; afd0c557ecaa091c1a84aac11865488b03a20dc0}, citeulike-linkout-0 = {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-728.html}, comment = {Cited in answer to 'Finding which triangles points are in':https://scicomp.stackexchange.com/questions/2624/finding-which-triangles-points-are-in?rq=1}, file = {brown_97_robust.pdf}, institution = {University of Cambridge, Computer Laboratory}, interhash = {7c2b26820221a9593ef90caf8edb6017}, intrahash = {3ae044305ed27cf6a0e894bddeb8314b}, issn = {1476-2986}, keywords = {65d18-computer-graphics-computational-geometry 65n50-pdes-bvps-mesh-generation-and-refinement}, number = {UCAM-CL-TR-728}, posted-at = {2018-10-29 00:39:48}, priority = {5}, series = {Technical Report}, timestamp = {2019-03-01T00:11:50.000+0100}, title = {{A Robust Efficient Algorithm for Point Location in Triangulations}}, url = {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-728.html}, year = 1997 }