Dartmouth College Computer Science Technical Report series CS home TR home TR search TR listserv By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z By number: 2018, 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

Voronoi Diagrams Based on Convex Distance Functions
L. Paul Chew, Robert L. Scot Drysdale
Dartmouth PCS-TR86-132

Abstract:

We present an "expanding waves" view of Voronoi diagrams that allows such diagrams to be defined for very general metrics and for distance measures that do not qualify as matrics. If a pebble is dropped into a still pond, circular waves move out from the point of impact. If n pebbles are dropped simultaneously, the paces where wave fronts meet define the Voronoi diagram on the n points of impact. The Voronoi diagram for any normed matric, including the Lp metrics, can be obtained by changing the shape of the wave front from a circle to the shape of the "circle" in that metric. (For example, the "circle" in the L1 metric is diamond shaped.) For any convex wave shape there is a corresponding convex distance function. Even if the shape is not symmetric about its center (a triangle, for example), although the resulting distance function is not a metric, it can still be used to define a Voronoi diagram. Like Voronoi diagrams based on the Euclidean metric, the Voronoi diagrams based on other nomed metrics can be used to solve various closest-point problems (all-nearest-neighbors, minimum spanning trees, etc.). Some of these problems also make sense for convex distance functions which are not metrics. In particular, the "largest empty circle" problem becomes the "largest empty convex shape" problem, and "motion planning for a disc" becomes "motion planning for a convex shape". These problems can both be solved quickly given the Voronoi diagram. We present an asymptotically optimal algorithm for computing Voronoi diagrams based on convex distance functions.

Note: This TR appears to have been lost. (April 2008)

This report is not available electronically.

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
L. Paul Chew and Robert L. Scot Drysdale, "Voronoi Diagrams Based on Convex Distance Functions." Dartmouth Computer Science Technical Report PCS-TR86-132, 1986.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu

Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.