NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Generating Voronoi Diagrams for Curved Shapes with Divide-and-ConquerVoronoi diagrams have been used in many practical applications including solid modeling, Numerical Control machining, Finite Element mesh generation, etc. Investigating the properties of these diagrams is an active research topic with many fruitful results. Computational techniques for Voronoi diagrams, however, have been concentrated on low order elements, for points, lines, polygons, quadratic curves and surfaces. This paper presents a divide-and-conquer scheme computing the diagrams for planar shapes bounded by closed curves commonly encountered in Computer Aided Design. These curves include analytical curves and splines. The algorithm first divides the boundary curve into sections, delimited by curve points with the minimal curvatures. Bisector branches for these sections are then generated and merged recursively to obtain the final diagram. A detailed example in the paper shows the steps of the generation and merging of the bisectors. A simple analysis of the complexity of the algorithm is also presented.
Document ID
20020041202
Acquisition Source
Ames Research Center
Document Type
Abstract
Authors
Chou, Jin J.
(MCAT Inst. Moffett Field, CA United States)
George, Michael W.
Date Acquired
August 20, 2013
Publication Date
January 1, 1996
Subject Category
Numerical Analysis
Meeting Information
Meeting: Solid Modeling 1997 Conference
Location: Atlanta, GA
Country: United States
Start Date: May 14, 1997
End Date: May 16, 1997
Funding Number(s)
PROJECT: RTOP 538-05-11
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.

Available Downloads

There are no available downloads for this record.
No Preview Available