Affordable Access

Publisher Website

Representing the Voronoi diagram of a simple polygon using rational quadratic Bézier curves

Authors
Publisher
Elsevier Ltd
Publication Date
Volume
27
Issue
8
Identifiers
DOI: 10.1016/0010-4485(95)99797-c
Keywords
  • Voronoi Diagrams
  • Curves
  • Rational Polynomials
Disciplines
  • Computer Science
  • Mathematics

Abstract

Abstract The Voronoi diagram of a set of geometric entities on a plane, such as points, line segments, or arcs, is a collection of Voronoi polygons associated with each entity, where the Voronoi polygon of an entity is a set of points which are closer to the associated entity than any other entity. A Voronoi diagram is one of the most fundamental geometrical constructs, and it is well known for its theoretical elegance and the wealth of applications. Various geometric problems can be solved with the aid of Voronoi diagrams. The paper discusses an algorithm to construct the Voronoi diagram of the interior of a simple polygon which consists of simple curves such as line segments as well as arcs in a plane with O( N log N) time complexity by the use of a divide-and-conquer scheme. Particular emphasis is placed on the parameterization of bisectors using a rational quadratic Bézier curve representation which unifies four different bisector cases.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

A simple method for approximating rational Bézier...

on Computer Aided Geometric Desig... Jan 01, 2008

Curvatures of the quadratic rational Bézier curves

on Computers & Mathematics with A... Jan 01, 1998

Voronoi diagrams and offset curves of curvilinear...

on Computer-Aided Design Jan 01, 1998

Polygon offsetting using a Voronoi diagram and two...

on Computer-Aided Design Jan 01, 1998
More articles like this..