Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Sorting Helps for Voronoi Diagrams
Authors: Chew, L. Paul
Fortune, Steven
Keywords: computer science
technical report
Issue Date: May-1993
Publisher: Cornell University
Abstract: It is well known that, using standard models of computation, it requires $\Omega(n$ log $n$) time to build a Voronoi diagram for $n$ data points. This follows from the fact that a Voronoi diagram algorithm can be used to sort. But if the data points are sorted before we start, can the Voronoi diagram be built any faster? We show that for certain interesting, although nonstandard types of Voronoi diagrams, sorting helps. These nonstandard types Voronoi diagrams use a convex distance function instead of the standard Euclidean distance. A convex distance function exists for any convex shape, but the distance functions based on polygons (especially triangles) lead to particularly efficient Voronoi diagram algorithms - fast algorithms using simple data structures. Specifically, a Voronoi diagram using a convex distance function based on a triangle can be built in $O(n$ log log $n$) time after initially sorting the $n$ data points twice. Convex distance functions based on other polygons require more initial sorting.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
93-1347.pdf1.62 MBAdobe PDFView/Open
93-1347.ps331.7 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us