A Sweepline Algorithm for Generalized Delaunay Triangulations

Research output: Book/anthology/dissertation/reportReport

  • Department of Computer Science
We give a deterministic O(n log n) sweepline algorithm to construct the generalized Voronoi diagram for n points in the plane or rather its dual the generalized Delaunay triangulation. The algorithm uses no transformations and it is developed solely from the sweepline paradigm together with greediness. A generalized Delaunay triangulation can be based on an arbitrary strictly convex Minkowski distance function (including all L_p distance functions 1 < p < *) in contrast to ordinary Delaunay triangualations which are based on the Euclidean distance function.
Original languageEnglish
PublisherDepartment of Computer Science, Aarhus University
Number of pages21
Publication statusPublished - 1991

See relations at Aarhus University Citationformats

ID: 37371755