3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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''? $\endgroup$
    – Ruchira
    Commented Dec 17, 2012 at 2:05
  • $\begingroup$ Ruchira: What happens to the length of $L$? It's convex, and thus cannot have a maximum inside the interval. $\endgroup$
    – Alexandre Eremenko
    Commented Dec 18, 2012 at 14:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .