dc.contributor.author Chew, L. Paul en_US dc.contributor.author Fortune, Steven en_US dc.date.accessioned 2007-04-23T16:29:21Z dc.date.available 2007-04-23T16:29:21Z dc.date.issued 1993-05 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1347 en_US dc.identifier.uri https://hdl.handle.net/1813/6117 dc.description.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. en_US dc.format.extent 1659596 bytes dc.format.extent 339659 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject computer science en_US dc.subject technical report en_US dc.title Sorting Helps for Voronoi Diagrams en_US dc.type technical report en_US
﻿