Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 http://dash.harvard.edu/bitstream/handle/1/4731601/Gibson_Control_Mitotic.pdf 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|improve this question
add comment

2 Answers

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.