Computing the center of area of a convex polygon

PETER BRASS and LAURA HEINRICH-LITAN

Abstract
The center of area of a planar convex set C is the point p for which the minimum area cut off from C by any halfplane containing p is maximized. Properties of this point were studied already long ago in classical geometry, but it is quite nontrivial to really determine this point for a given convex set. We give an O(n^2 (\log n)^3 \alpha(n))-algorithm to compute the center of area of a convex n-gon, which improves a previous O(n^6 (\log n)^2)-algorithm of Diaz and O'Rourke.

Technical Report B 02-10, Freie Universitšt Berlin, Fachbereich Mathematik und Informatik, 2002.