On constructing Delaunay triangulations for sets constrained by line segments

Excerpt from On Constructing Delaunay Triangulations for Sets Constrained by Line Segments T for S is a triangulation for S constrained by E if for each 6 in E and each t in T, e does not intersect I N T(t). Given T, a triangulation for S constrained by E, we say, that T is a Delaunay triangulation for S constrained by E if for each t in T there does not exist a point P of S inside the circumcircle of t such that no e in E intersects the interior of the convex hull of t U {p}. Delaunay triangulations constrained by line segments have been studied by Lee [7] and Chew for line segments that do not cross. Lee and Chew have also shown how to construct them in o(n (log N )2) and o(n log N) worst-case complexity, respectively, where N is the number of points in S. In this paper, we present an algorithm, based on a different approach, that computes this type of triangulation in expected linear time for fixed E. It consists of two steps. In the first step, a Delaunay triangulation for S is constructed by applying to S one of several existing algorithms In the second step, a sequence of triangulations for S, the last of which is the desired triangulation, is generated from the initial triangulation as each line segment in E is incorporated into the previously obtained triangulation. About the Publisher Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.