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

Deok-Soo Kim, Il Kyu Hwang, Bum Joo Park

Research output: Contribution to journalArticle

37 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)605-614
Number of pages10
JournalComputer-Aided Design
Volume27
Issue number8
DOIs
StatePublished - 1995 Jan 1

Fingerprint

Parameterization

Keywords

  • curves
  • rational polynomials
  • Voronoi diagrams

Cite this

@article{0058be7a1f524ec0afee9fa34a9c624f,
title = "Representing the Voronoi diagram of a simple polygon using rational quadratic B{\'e}zier curves",
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{\'e}zier curve representation which unifies four different bisector cases.",
keywords = "curves, rational polynomials, Voronoi diagrams",
author = "Deok-Soo Kim and Hwang, {Il Kyu} and Park, {Bum Joo}",
year = "1995",
month = "1",
day = "1",
doi = "10.1016/0010-4485(95)99797-C",
language = "English",
volume = "27",
pages = "605--614",
journal = "CAD Computer Aided Design",
issn = "0010-4485",
number = "8",

}

Representing the Voronoi diagram of a simple polygon using rational quadratic Bézier curves. / Kim, Deok-Soo; Hwang, Il Kyu; Park, Bum Joo.

In: Computer-Aided Design, Vol. 27, No. 8, 01.01.1995, p. 605-614.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Kim, Deok-Soo

AU - Hwang, Il Kyu

AU - Park, Bum Joo

PY - 1995/1/1

Y1 - 1995/1/1

N2 - 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.

AB - 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.

KW - curves

KW - rational polynomials

KW - Voronoi diagrams

UR - http://www.scopus.com/inward/record.url?scp=0029349763&partnerID=8YFLogxK

U2 - 10.1016/0010-4485(95)99797-C

DO - 10.1016/0010-4485(95)99797-C

M3 - Article

AN - SCOPUS:0029349763

VL - 27

SP - 605

EP - 614

JO - CAD Computer Aided Design

JF - CAD Computer Aided Design

SN - 0010-4485

IS - 8

ER -