A continuous center point of a convex spherical polygon

Question

In discrete geometry, the center point $c$ of a discrete set $S$ of $n$ points in the plane is such that any half plane containing $c$ contains (roughly) $n/3$ points of $S$. (Such a center point always exists.)

My problem is similar but in a continuous setting. I have a convex spherical polygon $P$ on the unit sphere. In this context an "area-center" point $c$ is such that any half sphere that contains $c$ also contains a part of $P$ whose area is at least a constant fraction of the area of $P$.

The definition can be similarly phrased with convex polygons on the plane and half-planes instead of half-spheres. It can also be generalised to higher dimension.

My questions are:

1. Does this definition has a well-known name? ("area-center point"?)
2. Do we know algorithm to compute such an area-center point? (exact or approximate)

(My motivation for finding such a point is for doing logarithmic search on the unit sphere.)

I ask this question here because searching the web only leads me to centroids or discrete center point, or the Tverberg generalization, but nothing related to the specific definition given above. (I have already asked question 30 minutes ago on math SE, but realised it is probably more relevant to comp. geom. hence its posting here)

Thank you !

Answer 1

For your second question...

For any distribution, if you take a sample $R$ of size $O(1/epsilon^2 )$ of it, and compute its center point, it is going to be a $\geq (1/3-\epsilon)$-center point, with probability $\geq 1-\epsilon^{O(1)}$ by the $\epsilon$-net theorem (well, more precisely the $\epsilon$-sample theorem). You can apply this to a polygon - you just need to sample points uniformly inside the polygon. This works in any constant dimension.

Similar ideas were used in the paper "Approximating Center Points with Iterated Radon Point". Or so I believe... ;)

Computing the exact center point for a general polygon is nasty as far as I know. There was a paper in the 90s by Dan Halperin on maintaining the area bisector of a polygon, and it was painful, if my memory serves me right.

Answer 2

Thank you Sariel. Your comment answers my first question and we can use the same name of centerpoint.

And I think I have a partial answer for my second question, for the planar case (as opposed to the spherical case). Let $P$ be a convex polygon and write $A(P )$ for the area of $P$. If we have a centrally-symmetric polygon $S$ inscribed in $P$ then any half-plane $H$ containing the center-of-symmetry of $S$ contains at least half of $S$: $A(P\cap H)\geq\dfrac{A(S)}{2}$.

So we want to find the largest such centrally-symmetric inscribed polygon. This is easy to do: the center-symmetric polygons of $P$ for various centers of symmetry are all translates of each other. So take any one of them and compute the translate of it, $P'$, that maximizes the overlap with $P$. This can be done efficiently (but approximately) using the algorithm of Ahn et al [here] .

It is easy to show that $S=P\cap P'$ is indeed the largest centrally-symmetric polygon inscribed in $P$.

There remains to show that $S=P\cap P'$ is large enough (i.e. constant fraction of $A(P )$). I found a paper by Jin and Matulef [here] whose theorem 2 implies that $A(S)\geq\dfrac{2}{\pi}A(P )$, which proves the existence of a centerpoint for planar convex polygons for which any half-plane that contains the centerpoint contains at least a fraction $\dfrac{1}{\pi}$ of the area of $P$.