Nearly convex sets and the shape of legislative districts. (English) Zbl 1170.68620

Summary: 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.


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52B55 Computational aspects related to convexity
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68Q25 Analysis of algorithms and problem complexity