Online Delaunay Triangulation Using the Quad-Edge Data Structure

Previous works involving the Online Delaunay triangulation problem required that the incoming request lies within the triangulation or a predefined initial triangulation framework, which will contain all the incoming points. No mention is made for Online Delaunay triangulation when the request point lies outside the triangulation, which also happens to be the unbounded side of the Convex Hull of the triangulation. In this work, we give a solution for the Online Delaunay triangulation Problem for incoming request points lying in the unbounded side of the Convex Hull bounding the Delaunay triangulation as well for points lying inside the triangulation. We use the Quad-Edge data structure for implementing the Delaunay triangulation.