Premium
How Big is an n ‐Sided Voronoi Polygon?
Author(s) -
Muder Douglas J.
Publication year - 1990
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms/s3-61.1.91
Subject(s) - voronoi diagram , mathematics , combinatorics , polygon (computer graphics) , centroidal voronoi tessellation , polygon covering , euclidean geometry , plane (geometry) , regular polygon , geometry , computer science , frame (networking) , telecommunications
It is well‐known that in a packing of unit circles in the plane, the smallest Voronoi polygon is a regular hexagon, and the smallest n ‐sided Voronoi polygon is a regular n ‐gon for n ⩽ 6. When n > 6, however, the smallest n ‐sided Voronoi polygon is not regular, and there is no known formula for its area. This paper gives upper and lower bounds on the area. These bounds are quite close for small n , and as n approaches infinity the ratio of the bounds approaches one. This allows us to conclude that if a n is the area of the smallest n ‐sided Voronoi polygon defined by a discrete set of minimum Euclidean distance 2, then a n / n approaches 1/π.