<p>For your second question...</p>

<p>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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2014-07-25T01:27:28.097Z
2014-07-25T01:27:28.097Z
Sariel Har-Peled
<p>Thank you Sariel. Your comment answers my first question and we can use the same name of <em>centerpoint</em>.</p>

<p>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}$.</p>

<p>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 <em>et al</em> <a href="http://dx.doi.org/10.1145/1064092.1064146" rel="nofollow"> [here] </a>.</p>

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

<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 <a href="http://2011.cccg.ca/PDFschedule/papers/paper3.pdf" rel="nofollow"> [here] </a> 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$.</p>

CC BY-SA 3.0
2014-07-24T23:51:21.057Z
2014-07-25T08:54:35.337Z
2014-07-25T08:54:35.337Z
Samuel Hornus
<p>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.)</p>

<p>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 <strong>area</strong> is <strong>at least</strong> a constant fraction of the area of $P$.</p>

<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.</p>

<p>My questions are:</p>

<ol>
<li>Does this definition has a well-known name? ("area-center point"?)</li>
<li>Do we know algorithm to compute such an area-center point? (exact or approximate)</li>
</ol>

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

<p>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. <em>(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)</em></p>

<p>Thank you !</p>

CC BY-SA 3.0
2014-07-24T13:42:31.003Z
The same question on mathSE : http://math.stackexchange.com/questions/876866/a-continuous-centerpoint-of-a-convex-spherical-polygon
Samuel Hornus
CC BY-SA 3.0
2014-07-24T16:10:10.657Z
Any distribution has a center point. The discrete case is just the easiest to state, and the measure/distribution case follows by a limit argument from the discrete case.
Sariel Har-Peled
CC BY-SA 3.0
2014-07-25T04:53:50.563Z
...or vice versa.
Jeffε
<computational-geometry>
A continuous center point of a convex spherical polygon
Samuel Hornus
# A continuous center point of a convex spherical polygon

(Asked by: username_0 on 2014-07-24)

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 !

**Tags:** computational-geometry
> **Comments:**
> **username_0**: The same question on mathSE : http://math.stackexchange.com/questions/876866/a-continuous-centerpoint-of-a-convex-spherical-polygon  
> **username_1**: Any distribution has a center point. The discrete case is just the easiest to state, and the measure/distribution case follows by a limit argument from the discrete case.  
> **username_2**: ...or vice versa.  

---

## 2 answers

### Answer by username_1 on 2014-07-25. Score: 3

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 by username_0 on 2014-07-24. Score: 1

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]](http://dx.doi.org/10.1145/1064092.1064146) .

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]](http://2011.cccg.ca/PDFschedule/papers/paper3.pdf)  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$.


---

