Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was redirected from math.stackoverflow.

So I am trying to teach myself discrete geometry and have started with the centerpoint problem. Could someone please help me understand computing centerpoints using Linear Programming using a picture and/or example. I do not find a good example of the basic LP formulation if centerpoint problem anywhere - either in the centerpoint literature or LP materials.

I hope this question can be asked here and that its level is okay.

Thank You

share|improve this question
What is a 'centerpoint problem'? –  copper.hat May 22 '12 at 16:58
I suspect the poster is asking how to find a "centerpoint", defined for finite sets in $\mathbb{R}^d$ as a point $x$ (not necessarily in the set) such that any half-plane containing $x$ must also contain at least $\frac{1}{d+1}$ of the points of that set. Rado (1947) proved the existence of such "centerpoints", a result known as the Centerpoint Thm. –  hardmath May 22 '12 at 17:06
@Hardmath Yes. I find lot of literature in this problem but since I am a beginner I want an example of LP applied to finding the centerpoint in a given finite point set P. –  Shakthi May 22 '12 at 18:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.