TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Thursday, August 28, 2008

Fair Partitions: N=3?

The conjecture: For any positive integer N, any convex polygon allows partitioning into N convex pieces so that every piece has the same area and same perimeter.

Our attempt on N=3 case of the conjecture (3 pieces):
----------------------------------------------------
0. Basic Observations:
--------------------------------
Every point P on the plane of *any* convex polygon has the property: For any P on or outside the polygon, we have *2 rays* starting from P which together cut the polygon into 3 pieces of equal area. If P is inside, we can find infinitely many sets of *3 rays* diverging from P which cut the polygon into 3 pieces of equal area.

Further, if P is in a 2-d region in the interior of the polygon, we can have at least 2 distinct ray triplets diverging from P which divide the polygon into 3 equal area pieces *with two of the pieces also having equal perimeter*.

1. 'Reflexive polygons'
-------------------------------
- We first look at 'reflexive polygons' ie. convex polygons with at least one reflection symmetry axis (isosceles triangles are the simplest examples of reflexive polygons).

(Property 1): It is obvious that *every* point on the infinite line containing the reflection axis of a reflexive polygon is the origin of 2 or 3 rays which divide the polygon into 3 pieces of equal area so that 2 of the 3 pieces also have equal perimeter.

Experimentally, we note a further property for this axis:
(Property 2): *Some* point(s) on the infinite line containing the reflection axis is the starting point of 2 or 3 infinite rays which divide the reflexive polygon into 3 pieces of equal area and *all three pieces* also having equal perimeter.

2. General convex polygons:
---------------------------------------
Our approach: We observed above that reflexive polygons allow the type of 3-partitioning we need; next we try to establish a specific structural property holds with no qualitative difference between reflexive and general convex polygons - this property could lead to the required 3-partitioning being possible for general polygons as well.

For a general convex polygon, we experimentally find that an *infinite continuous polyline* exists, passing thru the polygon, and sharing the Property 1 with the axis of reflexive polygons: *every* point on this polyline is the start of 2 or 3 rays which divide the convex polygon into 3 pieces of equal area so that 2 of the pieces also have equal perimeter.

Since for the general convex polygon there (experimentally) exists an infinite polyline which shares a crucial property with the axis of refelexive polygons (except that this is a polyline with bends, there appear no qualitative differences), we are led to believe that this infinite curve also has the Property 2, ie some point(s) on this infinite polyline also has 2 or 3 rays diverging which give 3 equal area pieces from the polygon with *all pieces* also having same perimeter. And that is what we need to prove.

3. Remarks on the 'polyline' for general convex polygons:
---------------------------------------------------------------------------

The infinite polyline mentioned above for general polygons is not unique. As noted in (0) above, there is a *2-dimensional region* in the interior of the polygon where every point gives at least 2 ray triplets which divide the polygon into 3 equal area pieces with 2 pieces also having same perimeter. So, within this 'core' region, the polyline is not unique.

We could prove: there exist at least 2 points (say A and B) on the boundary of the general polygon, from where 2 rays diverge dividing the polygon into 3 pieces of equal area with 2 of the pieces also having equal perimeter. And starting at A and B, we have 'semi-infinite polylines' going *outwards* and tending to diametrically opposite directions at infinity - with all points on these two half-polylines being start points of 2 rays with the same property as points A and B.

Experiments indicate that *between A and B* we have a continuous, 2-dimensional 'bridge region' thru the interior of the polygon with this property: every point in this bridge has 3 rays diverging from it and dividing the polygon into 3 pieces of equal area and with 2 of the pieces also having same perimeter. Such a bridge will guarantee the continuity of the infinte polyline.

Note: Such a 2-d bridge region in the interior exists for reflexive polygons as well and the axis passes thru this region.

0 Comments:

Post a Comment

<< Home