English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

On the Width and Roundness of a Set of Points in the Plane

MPS-Authors
/persons/resource/persons45509

Smid,  Michiel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Janardan,  Ravi
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

94-111.pdf
(Any fulltext), 162KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Smid, M., & Janardan, R.(1994). On the Width and Roundness of a Set of Points in the Plane (MPI-I-94-111). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B78A-7
Abstract
Let $S$ be a set of points in the plane. The width (resp.\ roundness) of $S$ is defined as the minimum width of any slab (resp.\ annulus) that contains all points of $S$. We give a new characterization of the width of a point set. Also, we give a {\em rigorous} proof of the fact that either the roundness of $S$ is equal to the width of $S$, or the center of the minimum-width annulus is a vertex of the closest-point Voronoi diagram of $S$, the furthest-point Voronoi diagram of $S$, or an intersection point of these two diagrams. This proof corrects the characterization of roundness used extensively in the literature.