Show simple item record

dc.contributor.authorChew, L. Paulen_US
dc.contributor.authorFortune, Stevenen_US
dc.date.accessioned2007-04-23T16:29:21Z
dc.date.available2007-04-23T16:29:21Z
dc.date.issued1993-05en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1347en_US
dc.identifier.urihttps://hdl.handle.net/1813/6117
dc.description.abstractIt 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.extent1659596 bytes
dc.format.extent339659 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleSorting Helps for Voronoi Diagramsen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics