MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a 2D convex polygon P and its centroid C, how do I find the longest line segment passing through C, where the endpoints of the segment lie on the boundary of P?

Intuitively I imagine there are only a small number of possibilities, so I could just compute the lengths of each of those line segments and see which is longest. For instance, I might check each such line segment passing through C where at least one endpoint is a vertex of P.

Background: I would like simulate an epithelial tissue represented as a collection of Voronoi cells. Per the mitotic cleavage plane during cell division lies along the "long axis", which I define above as the line segment I would like to find.

share|cite|improve this question

Your intuition is right: you only have to check the line segments through vertices. (Proof: the distance from a fixed point to a moving point on a line is a convex function of this moving point). This is also true for line segments passing through any other fixed point inside, it does not have to be the centroid. In general, this cannot be improved, unless you have some additional information about your polygon.

share|cite|improve this answer
That was what I had thought myself. But consider a line segment L through C lying perpendicular to one of the edges E of P and going through to another edge E' of P. Consider another line segment L' through C that lies perpendicular to E' and goes through to E. As the slope of the line segment L'' through C sweeps through the angles from L to L', the distance from C to E along L'' increases, since we are moving away from the perpendicular L, while the distance from C to E' along L'' decreases, since we are moving towards the perpendicular L'. What happens to the length of L''? – Ruchira Dec 17 '12 at 2:05
Ruchira: What happens to the length of $L$? It's convex, and thus cannot have a maximum inside the interval. – Alexandre Eremenko Dec 18 '12 at 14:42

Just a tangential remark: the longest segment through the centroid is not necessarily the longest segment in the polygon (not that anyone suggested it was), as the example below illustrates. The longest segment is known as the diameter of the polygon, for which there are efficient algorithms.
           Long segments

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.