IJPAM: Volume 49, No. 3 (2008)

NEARLY CONVEX SETS AND THE SHAPE
OF LEGISLATIVE DISTRICTS

James Bozeman$^1$, Lauren Pyrik$^2$, Julie Theoret$^3$
$^1$Lyndon State College
Lyndonville, VT 05851, USA
e-mail: james.bozeman@lyndonstate.edu
$^2$Esperanza Academy Charter High School
Philadelphia, PA 19140, USA
e-mail: lpyrik@neacademy.net
$^3$Johnson State College
Johnson, VT, USA
e-mail: julie.theoret@jsc.edu


Abstract.In this paper we examine how close a polygonal planar set is to being convex. This is accomplished by considering the ratio of the area of the largest convex set contained in the original polygon to the area of the convex hull of the set. Algorithms for determining the convex hull and for determining the largest convex set interior to the polygon are exhibited. After defining when such sets are nearly convex we then use this result to decide when legislative districts are nicely shaped.

Received: August 14, 2008

AMS Subject Classification: 52A10, 65D18, 68Q25, 68U05

Key Words and Phrases: convex set, convex hull, potato-peeling problem, redistricting

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2008
Volume: 49
Issue: 3