NDLI: Voronoi diagrams based on convex distance functions

Please wait, while we are loading the content...

An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles

The direct dominance problem

Output-size sensitive algorithms for finding maximal vectors

Decomposing polygonal regions into convex quadrilaterals

Halfspace range search: an algorithmic application of K-sets

On the partitionability of point sets in space (preliminary report)

Modeling planar configurations

New techniques for computing order statistics in Euclidean space (extended abstract)

Visibility and intersectin problems in plane geometry

Characterizing bar line-of-sight graphs

A method for drawing graphs

Computing the largest empty convex subset of a set of points

Dynamization of geometric data structures

Range searching in a set of line segments

Distance problems in computational geometry with fixed orientations

Sorting Jordan sequences in linear time

Rectilinear shortest paths with rectangular barriers

Planning the shortest path for a disc in $O(n^{2}log$ n) time

An efficient and simple motion planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers (extended abstract)

An improved algorithm for constructing kth-order Voronoi diagrams

Voronoi diagrams based on convex distance functions

A computational geometry approach to clustering problems

Voronoi diagrams and arrangements

Pyramid computer algorithms for determining geometric properties of images

Quadtrees, octrees, hyperoctrees: a unified analytical approach to tree data structures used in graphics, geometric modeling and image processing

Bounds for partitioning rectilinear polygons

On partitioning polygons

Finding minimal convex nested polygons

Turtlegons: generating simple polygons for sequences of angles

Computing a convex skill of an orthogonal polygon

The complexity of cutting paper (extended abstract)

Voronoi diagrams based on convex distance functions

Content Provider	ACM Digital Library
Author	Dyrsdale, Robert L. Scot Chew, L. Paul
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 metrics. 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 places where wave fronts meet define the Voronoi diagram on the n points of impact.The Voronoi diagram for any normed metric, 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. If the shape is not symmetric about its center (a triangle, for example) then the resulting distance function is not a metric, although it can still be used to define a Voronoi diagram.Like Voronoi diagrams based on the Euclidean metric, the Voronoi diagrams based on other normed metrics can be used to solve various closest-point problems (all-nearest-neighbors, minimum spanning trees, etc.). Some of these problems also make sense under 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.
Starting Page	235
Ending Page	244
Page Count	10
File Format	PDF
ISBN	0897911636
DOI	10.1145/323233.323264
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1985-06-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Bisectors and voronoi diagrams for convex distance functions (2000).

Voronoi diagrams of lines in 3-space under polyhedral convex distance functions

Voronoi diagrams of lines in 3-space under polyhedral convex distance functions (1995)

Planar Voronoi Diagrams for Sums of Convex Functions, Smoothed Distance, and Dilation

Voronoi Diagrams for Convex Polygon-Offset Distance Functions (2000)

Voronoi Diagrams for Convex Polygon-Offset Distance Functions (2000)

A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D

SERIE B INFORMATIK Voronoi Diagrams of Lines in Space Under Polyhedral Convex Distance Functions

Planar Voronoi Diagrams for Sums of Convex Functions, Smoothed Distance and Dilation

Voronoi diagrams based on convex distance functions

Similar Documents

Bisectors and voronoi diagrams for convex distance functions (2000).

Voronoi diagrams of lines in 3-space under polyhedral convex distance functions

Voronoi diagrams of lines in 3-space under polyhedral convex distance functions (1995)

Planar Voronoi Diagrams for Sums of Convex Functions, Smoothed Distance, and Dilation

Voronoi Diagrams for Convex Polygon-Offset Distance Functions (2000)

Voronoi Diagrams for Convex Polygon-Offset Distance Functions (2000)

A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D

SERIE B INFORMATIK Voronoi Diagrams of Lines in Space Under Polyhedral Convex Distance Functions

Planar Voronoi Diagrams for Sums of Convex Functions, Smoothed Distance and Dilation

Voronoi diagrams based on convex distance functions