Efficient/practical algorithms for geometric structures: Convex hulls, Delaunay triangulations and Voronoi diagrams

This Ph.D. dissertation focuses on four algorithms for constructing and/or maintaining three important geometric structures in the plane: convex hulls, Delaunay triangulations and Voronoi diagrams.; Golin and Sedgewick devised a simple pre-processing scheme to discard all of the points that are inside an axis-aligned rectangle, which serves as a quick preprocessing step to speed up any convex hull algorithm. We extend their idea by first computing an 8-gon approximation of the convex hull, and 5 disjoint axis-aligned rectangles are carefully carved out of the 8-gon. Our scheme is robust and less sensitive to the underlining point distributions and can be extended to 3D convex hulls.; Guibas, Knuth and Sharir proved that randomized incremental construction of the Delaunay triangulation (DT) of n points can be computed in O(n log n) expected time. We present the first efficient algorithm (O(log n) expected time per operation) that allows both point insertions as well as point deletions for the dynamic maintenance of DTs. The algorithm can be extended to higher dimensions.; We present an algorithm for the dynamic maintenance of DTs with constraint chords. Constrained DTs are practical extensions to DTs and are widely used in numerical grid generation and geographic data processing. Chew proposed the first O(n log n) time algorithm for building CDTs of n non-intersecting line segments and points, but it is not easy to generalize this approach to dynamic situations and is much harder to implement. Our C++ program can dynamically insert/delete constraint chords as well as points in the triangulation. The chord deletion function can be used to construct the Delaunay triangulation of n points (with or without constraint chords) in O(n log n) expected time.; We improve a previous O(kn log n) time and O(kn) space algorithm by Leven and Sharir for computing Voronoi diagrams (of n non-intersecting line segments and points) using a distance function defined by any k-sided convex polygon. We do this in optimal O(k + n) space and improved O((log{dollar}sp2{dollar}k)n log n) time.