Shortest bisecting line [closed]

Question

I have troubles finding this:

   

I don't know how to find this or even write algorithm to do this. Can you help me?

Thanks in advance

Answer 1

To make this a good question for this forum as well as a feasible problem, you should use words to specify the problem domain. Based on your picture, I would assume the problem is like this:

Let C be a convex polygon with n sides. Find L, a line segment contained in the convex hull P of C such that a) L union C represents the union of two convex polygons A and B, and b) the area of the convex hull of A is equal to the area of the convex hull of B, and both are equal to half the area of P, and c) all other candidate line segments meeting conditions a) and b) are at least as long as L or longer.

Now some inconclusive thoughts based on the description I just gave above.

Before you tackle the case of general n, you might see what is known or possible to prove with n equal to 3 and with n equal to 4. For n equal 3 you might ask whether L contains the point M which is the intersection of three medians (which are area bisecting lines of the triangle originating from one of the triangle vertices). If this is true, then a kind of sweeping line pivoting around M will have a length which is easily computed algorithmically, and will be parallel to a side in the case C is an equilateral triangle. (Note that I have not proved M lies on L. Indeed, this triangle suggests it does not.)

Even without the aid of M, you may ask yourself how the length of a bisecting line varies as you rotate the angle the line makes with respect to a given fixed line R. You may then find how to vary theta so as to find a local minimum. This approach is what leads me to conjecture that the line L is parallel to a side for the case of an equilateral triangle.

In order to have a "nice" algorithm for this, you will need a "nice" theorem. I suggest something like "Given C above sufficiently nice, a bisecting line L which emanates from a given edge of C must terminate at an opposing set of edges which are readily calculated." or "The set of bisecting lines emanating from an edge of C determine a region of C whose area is the length of the line times half the average value of the bisecting lines". You want some useful criterion on which to base an algorithm, and the closest I can come up with is that two bisecting lines of C must intersect and must divide P into four pieces of comparable areas (two pieces have area x, two have area y, and 2(x+y) is the area of P).

Gerhard "Meet In The Middle Somewhere" Paseman, 2018.10.14.