TECH-MUSINGS

Packing Rectangles

2012-02-07T03:27:00.001-08:00

Here is a puzzle to which I dunno the answer yet.

Claim: Given N (N>1) rectangles all of the same area but all with different perimeters.
We cannot pack them without gaps to form a large rectangle.

IOW, if a rectangle is broken into N smaller rectangles all of same area, at least two of the pieces are identical.

Remark: it is not too hard to show rectangles which can be divided into N equal area rectangles with just 2 pieces identical, and all others having different perimeter.

Perhaps the claim may be easier to prove under the constraint: the sides of the rectangle and the pieces ought to be integers/rationals.

The following pages may be of interest.
http://mathdl.maa.org/images/upload_library/22/Ford/Wagon601-617.pdf
http://www.math.uwaterloo.ca/navigation/ideas/articles/honsberger2/index.shtml

Congruent Partitions - A Special Case

2010-01-01T14:16:00.000-08:00

Question: Let us say, we cut from a convex polygon P 2 mutually congruent pieces such that the pieces have as great an area as possible. Find that polygon P which causes the maximum wastage - the fraction of the area wasted to the total area of P.

P is constrained to be convex with the pieces allowed to be non-convex. Which shape of P gives highest 'wastage fraction'? Basically, we need to upper-bound the wastage fraction when a convex P is 'maximally congruent bisected'.

A simple fact: The two maximum area pieces have to touch each other; indeed, otherwise both pieces could be moved in the interior of P (which is convex) to a config where neither piece touches the walls of P or each other - and from that stage, both pieces can be expanded identically => the area of the pieces were not max to begin with.

Another Congruent Partition Problem

2009-10-24T21:18:00.000-07:00

A bit of news: The basic Congruent partition problem has been listed at:
http://maven.smith.edu/~orourke/TOPP/P73.html

Question: Given a convex polygon P and a number N so that P can somehow be cut into N mutually congruent *non-convex* pieces with no wastage - ie. a 'perfect congruent partition' exists for P for that N. Then is it true that P necessarily also allows a partition into N mutually congruent convex pieces?

In other words, can we say: "there is no P and N such that P can be perfectly congruent-partitioned into N pieces only when the pieces are necessarily non-convex"?

For N = 2, the above question seems to have an affirmative answer - no convex polygon appears to have only a congruent 2-partition such that pieces are non-convex. Beyond N=2, nothing much seems to be known.

'Congruent' Partitions of Polygons

2009-05-04T05:36:00.000-07:00

Here is another polygon partitioning problem, a work-in-progress thought:

Problem: Given a polygon P and an number N. We need to cut from
P, N mutually congruent (*) pieces (or 'tiles')of a suitable shape such that the area inside P is as fully covered by the pieces as possible.

(*) - two polygons are congruent if one can be made to
coincide totally with the other by translation, rotation or 'flipping
over'.

Note 1: It is known that a convex polygon *need not* admit a partitioning into N congruent pieces which together cover the whole of its interior. eg:
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/December2003.html
(Part 2 of the 'challenge').

Guess: It seems this inevitability of there being a left-over (in some cases)is a 2D phenomenon. Any 3D input region appears cuttable into, say, 2 (or any N) identical and non-convex pieces which fill the whole of the input region in a very fractally way with dense and interpenetrating branches (somewhat like the two worms which eat up an anpple in Gamow's '1,2,3,infinity').

So, the problem requires us to choose the shape the identical pieces should have so
that as little area of the input polygon is left uncovered - or the
input sheet is as fully 'utilized' as possible.

-----------------
Further thoughts:
-----------------

1. Consider the following claim: for any N and for any input *convex* polygon, if we do the 'congruent partitioning' with the further condition that the identical pieces are also convex and find the best solution, it will also be the global optimum - ie. allowing the pieces to be concave leads to no better utilization of the input convex polygon.

This claim - that the best congruent partition of a convex polygon can be done with convex pieces - is *not true* it appears (thanks to Prof. Erich Friedman).

eg: Consider a 3X7 rectangle and remove a unit square from a corner; then form the *convex hull* of the resulting object, getting a pentagon or area 20.5. Out of this, an area of 20 can be filled by five L-tetrominoes - non convex objects. No convex congruent partition of this pentagon appears to leave such a small remainder.

Now, we float a new guess: the complexity of the piece (measured in the number of edges in it) in the best congruent partition is not more than linear in the complexity of the input polygon (here, Circular arcs are treated as no more complex than straight lines). There *probably* is no dependence of the complexity of the piece on N, the number of pieces. Basically, the guess is that if the input polygon has a 'simple' shape, the pieces in the best congruent partition cannot be highly branched and complex but comparable in complexity to the input polygon itself, for any N.

-----

2.If we relax the original requirement - to give N mutually congruent tiles - and seek N mutually identical *sets of tiles* (every tile of any set i is congruent to a tile in any other set j as i and j run from 1 to N), with each tile-set allowed to have finitely many pieces, we can do better in terms of reducing leftover:

Fact: Any triangle can be cut into 4 mutually congruent triangles; and any polygon can be divided into triangles. Any m-gon will give m-2 triangles.

So, If N is 4, we can triangulate the (m-vertex) input polygon and further divide each triangle into 4 so as to achieve a partition into 4 tile-sets each with m-2 triangles. This is easily generalizable to N = any power of 2. No bit of the input polygon is wasted.

Definition: A polygon is n-sectible if it can be cut into n mutually congruent pieces.

If N=3, we could try this: Somehow partition the input polygon into *some* number of pieces (each of which may be quite different from each other) such that each of them is 3-sectible; that will in turn enable a partition into 3 mutually identical sets of pieces with no leftover.

Note 1: 3-sectibility is a very loose property and is shown by a wide range of shapes. And it is not clear if any given polygon *always* allows partitioning into 3-sectable pieces (or in general, partitioning into m-sectable pieces) with no leftover.

Note 2: Even the apparently simpler (to state) problem: "given a polygon, determine if it is 3-sectible" appears unexplored - although there is work on partitioning a polygon into 3 pieces all of same area and same perimeter (eg: in the 'fair partitioning' context).

A Doubt On Circle Packing

2009-04-25T11:20:00.000-07:00

We understand that for packing identical circles (indeed packing copies of any centrally symmetric convex shape) in an infinite plane, the best arrangment is a always a lattice arrangement (hexagonal lattice for packing circles).

Does the above lead naturally to the following?

Consider any specified 2d shape as a container for identical circles.

Claim: Some finite critical magnification(scaling) of this shape exists such that
1.the best packing in it of circles is a hexagonal lattice of circles arranged inside and
2.for any further scaling up of this shape the best pack is the hexagonal pack.

This implies: If the container is a square, there is some critical size of the square beyond which the best circle packing of unit circles is ALWAYS the hexagonal lattice.

Some more thoughts on 'automatable' arrangments to follow...

Update (3rd May 2009): The main guess above is invalid. For the square the hex lattice is tbe best packing only in the asymptotic limit, as the square goes to infinity and is the same as the plane itself. No finite threshold and stuff. This is a bit surprising to me but that is how things probably are!

Fair Partitions - Article

2009-02-13T23:30:00.000-08:00

After all those 'work in progress' posts on the polygon partitionig problem we posed (a series which went on for well over a year), we collected whatever we thought up into a proper article. It can be read at:

http://arxiv.org/abs/0812.2241

Note: The article is on the longer side since we try to develop the themes at a leisurely pace and try to give several illustrative examples. Hope it reads well, and even more importantly, that our arguments are logically tight. Right now, the jury is out...

Fair Partitions - 2^N?

2008-09-07T00:43:00.000-07:00

We (Ramana Rao and self) consider here a recursive scheme for extending our polygon partitioning conjecture to 2^N. This approach is a variant of a naive recursion on N=2, which does not work - as argued in the post 'Fair Partitions -V':

------------
The conjecture: Given any positive integer N, any convex polygonal region allows partitioning into N convex pieces such that every piece has the same area and perimeter.
------------

Definitions:
-----------
We define a 'diagonal', as a line that divides a convex polygon into two pieces of equal area; their perimeters could be different (the diagonal could be between any two points on the boundary, not necessarily vertices).

Let us further call a line which divides a convex polygon into 2 pieces of equal area and equal perimeter a 'fair bisector'. Of course, a polygon can have just one fair bisector ( eg: for an isosceles triangle with very narrow base), a few or even infinitely many (a square for example) depending on its symmetry.

The Scheme:
----------
Divide input polygon into two equal area pieces by a diagonal; call these pieces A and B. Consider a *fair bisector* of piece A, dividing A into {A1, A2} - where A1 and A2 have equal area and equal perimeter. Likewise consider a fair bisector of B which gives pieces {B1,B2}. Initially, let us say the pair of pieces A1-A2 have higher perimeter than the pair B1-B2.

Rotate the *diagonal* continously; then, the pieces A and B change continuously maintaining equal areas; the two fair bisector lines also keep changing. Finally the diagonal reaches a position that is perfectly reverse of its initial position. Now, pieces A1-A2 have less perimeter than pair B1-B2 - they have merely exchanged their initial positions. By a continuity argument, we have somewhere along the rotation of the diagonal, a state where the two pairs had the same perimeter.

This could settle the conjecture for N= 4. Repeating the recursion, we could even prove the claim for N= 2^n. And if the conjecture could be proved for any number m, this could give a ready extension to N= m * 2^n

Possible Catch:
--------------
It needs to be shown that if a polygon is *continuously changed*, its fair bisector(s) change continuously - by a line segment moving continuously, we mean both its end points move continuously (of course, the length, orientation,etc of the segment as a whole could change).

Take a square and slightly and continously make it asymmetric, keeping its area constant; the new polygon might have only a few or just one fair bisector. this means most fair bisectors have simply *disappeared* by a continous transformation.

A more general case:

Consider a case where the fair bisector of piece A is such that sub-piece A2 covers the bisector entirely, ie. the fair bisector of A connects two edges of the input polygon and does not touch the diagonal which demarkates A and B.

Now let diagonal rotate a little, continuously, keeping the areas of pieces A and B same.Then, perimeter of piece A2 changes while A1 is *unaffected*. Of course, the areas of A1 and A2 remain equal. The net result: a difference just begins to develop between perimeters of A1 and A2.

Now, we need to change the fair bisector between A1 and A2 continuously to cancel out the perimeter difference that has emerged (due to the rotation of the diagonal) between A1 and A2. And we need a guarantee that such a continous change is possible for the entire rotation of the diagonal. What we need to prove is: at least one fair bisector of piece A - call this b(A) - and a fair bisector of piece B - call this b(B) - are such that as diagonal moves by a total of 180 degrees, b(A) continuously moves to b(B); a further movement of 180 of diagonal will cause b(B) to return to b(A).

Note : The new recursive scheme puts a constraint on the fair partitioning, a constraint we were not keen to put:

A general convex partitioning need not have two pieces meet in the interior of the polygon at 180 degrees - they only need to be convex.

In the recursive scheme A1 and A2, if they meet in the interior of polygon, are forced to together form an angle of 180 degrees. In the final partitioning, two pieces A1 and A2 together are forced meet the other two pieces along a straight line.

Update (12-9-08):
----------------
Let us call fair bisectors which are the result of symmetry and which cannot change continuously (and which merely vanish) when a polygon is slightly changed, 'bad bisectors'; those fair bisectors which do change continuously are good ones.

Our scheme seems to need the following to hold: Given two equal area convex polygons which share an edge (and together form a convex polygon). The number of 'good fair bisectors' of both these polygons are necessarily equal.

Indeed, if at a given position of a *diagonal*, the two equal area pieces A and B have different numbers of good fair bisectors, we would begin to doubt if one of A can actually continuously change all the way to one of B (as the diagonal does a 180 degree sweep) and vice versa.

Example:
We could check that the pentagon formed by points:
{(0,0),(6,20),(12,0),(12,-7.947),(12-.92, -19.39075)} has 3 good fair bisectors.
Consider the triangle:
{(0,0),(12-.92, -19.39075),(7,-55.53)}.
This triangle shares an edge with the pentagon, has the same area and together with the pentagon forms a convex polygon.
=> the common edge is a 'diagonal' of the big polygon formed by the pentagon and triangle.

Now, the triangle has only one fair bisector =>
some evidence that when the diagonal moves thru 180 degrees, the fair bisectors *need not* evolve continuously throughout the evolution of the diagonal.

Update (October 22, 2008):
-------------------------
Further experiments have confirmed that the fair bisector(s) of a polygon *may not* evolve continuously as the polygon is continuously deformed (keeping its area constant). But, (crucially!) for this new recursive scheme to work, we do not really need the fair bisectors to keep changing continuously - only the *perimeters of the pieces resulting from the fair bisectors need to change continuously*. In all examples tested so far, the perimeters do change continuously.

No logical proof yet either that the perimeters of pieces resulting from fair bisection of a polygon necessarily change continuously when the polygon itself is changed continuously. Work in progress...

Fair Partitions: N=3?

2008-08-28T03:40:00.001-07:00

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.

Fair Partitions - VII

2007-11-24T01:36:00.000-08:00

This is a status report on the fair partitioning business.

First, a bit of speculation. We have been trying to prove the convex fair partitioning conjecture ("given any integer N, any convex polygon allows paritioning into N convex pieces all of equal area and perimeter") for N=3 - ie. fair partitioning into 3 convex pieces.

In an earlier post, some continuity-based speculations had been floated. Now we think the following could work:

- There is a *large region* in the plane of the convex polygon (this large region includes a portion of the interior of the plane and also *most* of its exterior), the points P of which satisfy: (1) the polygon can be cut into 3 convex pieces of equal area by 3 rays diverging from P with (2) the extra requirement that one of these rays goes in the +X direction.

- Call the three resulting equal area convex pieces 1, 2 and 3, measured counterclockwise from the +X direction and their perimeters, P1, P2 and P3.

- There will be a continuous region in the plane so that for points there (as the sources of the rays) P1 is the greatest (ie. piece 1 has most perimeter), a region where P2 is greatest and likewise for P3. We could label these regions by P1, P2 and P3.

- We *guess* that from the P1 region we could go continuously either to the P2 region or to the P3 region; likewise from the P2 region we could cross over continously to P1 or P3 region and likewise for P3 region. This guess implies, there are dividing curves between the regions where P1=P2, P2=P3 and P3=P1 *and also* that these curves are bound to intersect. An intersection point between two of the curves is a meeting point from where 3 diverging rays, with one ray in +X do a convex fair partitioning of the given polygon.

Note 1: The angles between the rays need not all be less than 180 degrees. The pieces of the convex polygon that result should all be convex. That is all. Moreover, the ray in +X direction from the meeting point need not touch the polygon.

Note 2: Three such regions where each of P1, P2 and P3 are maximum, are expected to be present at least for one orientation of the polygon with respect to the X axis. That is sufficient for at least one meeting point for the rays and a partitioning of the type we need.

------------------
Now, we try to explicitly do some special cases of convex fair partitioning.

A. A regular hexagon into 7 pieces all of equal area and perimeter.

Consider the 'extreme configurations':

1. config 1: Hexagon of side 1, kept with a vertex, call this vertex 1 at the bottom and another - this is vertex 4 - at the top. A square (the area of this square has to be 3/7 of the hexagons) kept as a diamond inside the hexagon so that the centers of both coincide and a diagonal coinciding with diagonal 1-4 of the hexagon. The square can be divided into 3 identical rectangles and the rest of the hexagon into 4 identical pentagons.

In above state, the perimeter of each of the 3 rectangles constituting the central square is 2.81388. The perimeter of the 4 pentagons is 2.92894.

(the calculation uses the formula area of full hexagon = 6*sqrt(3)/4. and area of square is 3/7 of this and some basic trigonometry).

2. The other extreme config (config 2)is: Big regular hexagon unchanged. The square in the middle (appearing as a diamond) is gradually stretched vertically into a rhombus (of course, keeping its area constant)with the longer diagonal eventually coinciding with diagonal 1-4 of the regular hexagon.

The rhombus has the same area as the square of config 1 from which it is deformed. and the rhombus can be cut into 3 mutually identical parallelograms. the rest of the hexagon outside the rhombus can be obviously cut into 4 mutually identical quadrilaterals.

In this state, the perimeter of each of the 3 parallelograms which form the inner rhombus is 3.05208. the perimeter of each of the 4 outer pieces is now 2.95382.

Conclusion: config 2 can be reached by continuously deforming config 1. Throughout the deformation, the inner rhombus gives 3 identical parallelograms and the rest of the hexagon is formed of 4 identical pieces. In config 1, the 3 inner pieces have *lower* perimeter than the 4 outer pieces. In config 2, the 3 inner pieces have *greater* perimeter than the outer pieces. So, by continuity, there is a intermediate state where the perimeters of the two sets of pieces are equal. That settles the regular hexagon into 7 pieces case. If N = 5, the above continuity argument will still work with the square deformed into a rhombus as before but with area 1/5 of the big regular hexagon.

B. An equilateral triangle into 5 convex pieces:

Consider an equilateral triangle of side 5 units.We begin by dividing a side of the base AB of the triangle (any side can be the base) into 5 equal parts and connecting the dividing points to the opposite vertex, the apex C. Now, if we number the 5 pieces left to right as 1,2,3,4,5, extreme pieces 1 and 5 have max perimeter and the central piece 3 has least. All pieces have the same area.

Consider pieces 1 and 2 together as a single large triangular piece. We find that we can divide this piece into two pieces 1' and 2' of equal area and also equal perimeter by a line from a point on its side (segment AC) at a distance 0.4098 from the apex C to a point on the base at a distance 1.0892 from vertex A (basically, original piece 1 has had its base increased from 1 unit and height reduced keeping area constant but so that its perimeter reduces a bit).

Now, surprisingly, the perimeters of 1' and 2' are found to be exactly equal to that of central piece 3 which has not been touched. The areas of all pieces 1',2' and 3 are anyway equal. The same strategy employed to pieces 4 and 5 together finishes the partitioning.

Fair Partitions - VI

2007-08-24T03:00:00.000-07:00

We countinue on the conjecture:

"For every positive integer N, any convex polygon allows breaking into N convex pieces so that all pieces have the same area and same perimeter."

------
We recall the Definitions: Fair partition is a partition of a polygon which leaves all pieces with equal area and perimeter. A convex fair partition is a fair partition where all pieces are also convex.

We wondered if among all fair partitions possible for a convex polygon, the one with the least total perimeter of pieces - or least length of cuts - is a convex fair partition. But this appears to be *NOT* the case, at least for small N.

eg: Consider an isoscles triangle with base 1 and altitude 2 (the equal sides are then sqrt 5 each). Join a square of side 1 to the base to form pentagon. The area of this pentagon is 2 units. Take N = 2. ie we need to break the pentagon into 2 pieces of equal area and perimeter.

By inspection, the *only* convex fair partition is by the bisector of the apex of the isosceles triangle. And the length of the cut is 3 units. Now, it is possible to have another fair partitioning of the pentagon into one convex and one non convex pieces with cut length just around 1.7 units - considerably less than 3. So, the convex fair partitioning is not the 'best'.

The reason for considering the above line of thought was this: if somehow one can prove that for any non convex fair partitioning, there is always a better fair partitioning (better means one with less total of cut lengths) that can be achieved by tweaking one of the non convex pieces (and the remaining portion of the input polygon), we could have argued: "There definitely has to be *some* fair partitioning that has the least total of cut lengths. If any non convex fair partitioning can be improved, the fair partitioning with least cut lengths has to be one with no non convex pieces. This establishes the existence a convex fair partition thus proving the original conjecture".

But things do not appear to be so simple!

Fair Partitions - V

2007-07-27T03:35:00.000-07:00

Here is a bit more on the conjecture we had formulated a while ago:
"For every positive integer N, any convex polygon allows breaking into N convex pieces so that all pieces have the same area and same perimeter."

The news is that it has been listed as an open problem (with rather different wording) at http://maven.smith.edu/~orourke/TOPP/P67.html#Problem.67

We have two more small findings (tentative) to report:
1. For any N, any convex polygon can be divided into N convex pieces all of equal perimeter (not looking at their areas) by a family of suitably spaced parallel lines of any orientation => there are infinitely many ways of cutting the convex polygon into N convex pieces of equal perimeter - just like there are infinitely many ways to cut it into N convex pieces of equal area. This appears to add strength to the conjecture.

2. We made the following proposition: Given two convex polygons P and Q of equal area and perimeter *which together form another convex polygon*. Let P be cut into P1 and P2 where the two pieces have equal area and perimeter and Q, similarly into Q1 and Q2. We can have some pair of partitionings which make P1, P2, Q1 and Q2 all of same area and perimeter.

If this proposition can be proved, the main conjecture can be proved for N = any power of 2.
However, it appears that the above proposition is not necessarily true, at least as far as we can make out. So, the conjecture retains its mystery.

------------------------------------------------------------------------------------
Apparent Failure of N=2 to *recursively* generalize to N = 2^N in a straightforward manner
------------------------------------------------------------------------------------
Example:
------------
- Polygon P1 is an isosceles triangle with a narrow base.
- Polygon P2 is a *trapezium* with same base length and one base angle equal to 90 degrees. P2 also has slightly less 'height' than the triangle P1; we can now adjust its other sides so that both P1 and P2 have same area and perimeter.

- Now, consider the large convex polygon P formed by joining P1 and P2 along their bases.

We find that P has exactly *3 bisections* so that the 2 resulting pieces have both equal area and perimeter (the obvious parition into P1 and P2 themselves plus 2 other partitions). In the specific numerical example we tried, *none of these 3 bisections* seems to give two pieces, which when bisected further gave 4 resultant convex pieces all with same area and perimeter - the final 4 pieces all have same area but their perimeters always come in 2 mutually different pairs.

A specific numerical case:

P1, the triangle has vertices: (0,0), (6, 20), ( 12, 0);
P2, the trapezium has vertices: (0,0), ( 12, 0), ( 12,
-18.992), ( 11.3631,-18.992);

For large polygon P, formed by joining P1 and P2 along (0,0) - (12,0), we find P can be cut into 2 convex pieces of equal area and perimeter in 3 different ways.

- by the the obvious line joining (0,0) and (12,0)
- the line joining (0.50602,1.68673) and (12, -1.76073).
- the line joining (2.50594,-4.18836) and (10.5974,4.67521).

We considered each of these 3 bisections of P and looked at further bisections of the 2 resulting pieces. Numerically, in none of these cases could we find 4 resultant pieces all of same area and perimeter.

Fair Partitions - IV

2007-06-09T02:18:00.000-07:00

After a longish gap, we continue on the conjecture:
"For every positive integer N, any convex polygon allows breaking into N convex pieces so that all pieces have the same area and same perimeter."

1. Proof for N=2 (easy, although full of English)
------------------------
*Any* point on the perimeter of the convex polygon P, there is another point Q (call this the 'opposite point to P1') so that the line P-Q (direction important) divides the polygon into two equal area convex pieces. the two pieces will in general have different perimeter.

Let us begin with a specific point P1 on the boundary - its opposite point is P2. say, the equal area piece to left of cut line P1-P2 has greater perimeter.

Now, we move P1 along the perimeter (clockwise, say, does not matter which way). the opposite point P2 also moves in the same direction around the perimeter. Obviously when P1 reaches the initial position of P2, P2 will be at the initial position of P1. and now, the half area piece to the *right* of P1-P2 has greater perimeter, the opposite to what we started with. In other words, the difference between the perimeters of the two equal area pieces has changed sign.

So, assuming the perimeters of the two pieces change continuously (obvious), we have some position in between when the two equal area pieces of the polygon also will have equal perimeter - when the difference between perimeters is zero. QED.
-----------
2. The following 'restrictive sequential' approach will not work in general for general N:

First cut a convex piece off *leaving behind a convex piece*. Then break a convex piece of same perimeter and area off the remaining piece, again leaving behind a convex piece. Repeat the process N-1 times.

eg: If a circular disc is to be broken into 3 pieces of equal area and perimeter (N=3), *if the first cut should leave behind a convex piece*, the first cut is necessarily a chord which breaks off 1/3 area of the disc. Now, it appears the remainder can be broken into two pieces with mutually equal area and perimeter *only* by making them congruent (identical) to each other. There is only one way of doing so and the resulting two pieces won't have the same perimeter as the piece broken first.
-------------
3a: A special case. N=3, the input polygon is a square. Here we arrive at a solution different from the obvious one of "two parallel cut lines". This approach led us to the claims set out in case 3b below.

We look at two extreme cases. (1) Consider two cut lines parallel to a *diagonal* of a square and equally spaced with respect to that diagonal (call this diagonal AB) and which cut the square into 3 equal area pieces. The middle piece is now a flat hexagon and the two *congruent* outer pieces are triangles. We note that the middle piece has more perimeter than the outer ones.

(2) Now choose an end point of the above diagonal, say A. Slide the end points of both cut lines which lie nearer to A, towards A. We simultaneously adjust the cut lines so that the two outer pieces and the middle piece continue to have equal area (and also keeping the outer pieces mutually identical so these two pieces continue to have equal perimeter). The ends of the cuts eventually meet at point A. Now, the merge the end points which have met and continue move them together along diagonal AB towards B. The middle piece now is a quadrilateral and the side pieces also have become quadrilaterals. Finally a configuration is reached when the middle piece is a *square* of side a/sqrt(3) and the side pieces are two mutually identical trapeziums. At this point, the middle piece has *less* perimeter.

Since we have changed the cuts continuously, the perimeters of the pieces must have changed continuously. And the perimeter of the middle piece, initially greater than the other two has changed to be less. So, in between, there is some position where the perimeter of the middle piece equalled that of the two side pieces.
----------------

3b. Thoughts on the N=3 case (this is tentative and might be knocked out by a counter; still am documenting our thoughts, for completeness). We present a chain of claims:

- From any point on the boundary of a convex polygon, we can draw two diverging lines which divide the polygon into 3 equal *area* pieces (obvious).

Consider a point P on the boundary of a convex polygon and the three equal area pieces generated by diverging lines starting at that point. We number the three pieces 1,2,3 in say, clockwise order as viewed from P.
Claim 1: we can always find at least one P on the boundary of the input polygon so that the 'outer' equal area pieces *1 and 3* will also have equal perimeter.

Note: there are convex polygons for which the middle piece 2 never has same perimeter as the others - for example a circle. And we *do not* look at diverging lines which yield same perimeter for pieces 1 and 2 and a different value for piece 3.

Claim1 is provable from continuity.

- Now, we stand at a point P so that two lines diverging into the polygon divide the polygon into three equal area pieces and pieces 1 and 3 have same perimeter. now, consider the two fan shaped regions formed by the two cuts (the interior of piece 2 and its opposite region in the exterior of the polygon).

Claim 2: we always have a curve (maybe even a line) passing thru P and extending into the two fan shaped regions meeting at P so that from every point on this curve, we can have a Y formed by three cut lines meeting inside the polygon (if the point is inside polygon) or a V (if outside) so that all pieces are convex and the pieces 1 and 3 continue to have equal perimeter - ie. a curve along which the perimeter of peces 1 and 3 vary equally from their value at P (and all continue to be convex and also have same area). We are not sure about claim 2 although it looks correct due to the convexity of the input polygon and the way we have chosen P.

Claim 3: The two values of the perimeters ({p(1) and p(3)} and {p(2)} vary continuously }on the curve described in claim 3, and there will always a point so that all the 3 perimeters are the same. That is all.

A Different 'Center' To A Polygon

2007-04-19T04:42:00.000-07:00

In the last post here, we pondered (without nailing to the wall), the problem of finding the point inside a convex polygon which maximizes the minimum angle subtended there by the edges of the polygon. Now, we have something else on similar lines.

Problem: Given a convex polygon, find the point in its interior for which the sum of distances to the vertices of the polygon is least.

Thoughts: The required point need not be the centroid of the polygon.
---------
Example. consider a convex polygon formed by (1) 100 points extremely close to each other - so close that they are separate only at near infinite zoom - near the point x=-1 on the X axis, (2) another 100 points similarly close to each other but near the point x = +1 on the X axis and (3) a single point on the Y axis at Y = 201. Of course, the close by points lie so that the total set of 21 points form a convex polygon - from a distance this polygon looks like a triangle though.

Now, the centroid of this polygon is very close to a point on Y axis: y = +1. this centroid is at a distance 200 from the lone apex point and nearly sqrt(2) distant from the other 200 points. Now, consider the mid point of the base of the polygon, lying between the two point bunches at x = +/-1. This mid point is at distance 201 from the lone apex point but only at distance equal to nearly 1 from the other 200 points. Its distance sum is clearly less than that of the centroid.

------------

It might be interesting to see how this distance sum function varies across the region of the polygon in various cases. If I understand right, Earnshaw's theorem probably implies Sum (reciprocals of distances from vertices) has no proper minimum in the interior (only saddle points). Maybe something similar could be said about the distance sum as well.

Note added on May 23rd: Earnshaw's theorem is, as far as I know, a consequence of the electrostatic potential satisfying Laplace equation. The present problem has a potential that increases linearly with distance from the 'charge' and this *does not* satisfy Laplace equation. Hence there can very well be local maxima and minima for the distance sum function in the interior of the polygon. I know of no case where the *maximum* of the (sum of distances from vertices) is somewhere in the interior of the convex polygon - here we look at only the interior of the polygon and its boundary, not exterior.

Note added on July 5th 2007: Experiments indicate that the point which minimizes the sum of distances from the vertices has a unique position (there are no local minima etc for this distance sum function) . This appears true not only when the vertices are those of a convex polygon - any distribution of points (call them vertices)appears to have this property: a unique point minimizes the sum of the distances from these vertices.

And here is some further perspective from 'Mathworld':
"A convex function is a continuous function whose value at the midpoint of every interval in its domain does not exceed the arithmetic mean of its values at the ends of the interval."
This implies a convex function has to have at most one local minimum in its domain. I remember hearing that distance is a convex funtion (not sure about the proof) and probably, so is the sum of distances. Thus, we could say:
"Given a distribution of vertices on a plane and a point P which varies along any straight line. The sum of the distances from P to the vertices has a unique minimum on its straight line path. And since for P running along *any* straight line path in that plane, the distance sum function has a unique minimum, the function has to have a unique minimum *for the plane as a whole*.

Note added on December 12th: If the input polygon is a triangle, this problem is called the Fermat's problem. In this special case, the solution also solves the Steiner tree problem. Coxeter has described this special case in his 'Intro to Geometry' and proved the point is such that all the 3 sides of the triangle subtend 120 degrees there. And this wikipedia article has more details: http://en.wikipedia.org/wiki/Geometric_median

A Triangulation Problem

2007-04-05T03:14:00.000-07:00

The following problem was posed by Anurag. Thanks to Ramana Rao for his inputs.

--------
Given a convex polygon, how does one choose a point in its interior so that the least angle subtended at this point by the edges of the polygon is a maximum?
--------
Our present line of thought is:
1. Choose a variable point, say P at any location in the interior of the polygon and note the smallest angle subtended by the sides there. Note this side as S.
2. Move P towards this side S - so that the angle subtended by S at P keeps increasing, until the angle subtended by another side S' at the current point equals that subtended by S. Note the present position of P.
3. Now we need to further search in the intersection region of two circles - C passing thru the end points of S and P and circle C', that passes thru the end points of S' and P. Of course during this further search, we also need to see if any other edge of the polygon S'' subtends a smaller angle than S and S'.

The two circles intersect at another point apart from P, say P'. It appears that the best position of the point we need is not necessarily on the line joining P and P' (if we understand right, the reason is related to the locus of points at which two line segments subtend equal angles not being a straight line and being apparently governed by a higher degree polynomial) . So, we might need to search exhaustively the intersection region of the two circles.

To sum up, we do not know the best possible answer and the above method may be seriously flawed!

Note added on July 5th 2007: Experiments indicate that maximizing the minimum angle subtended by the edges of the polygon leads to a unique optimal point. In other words, the function: "minimum among the angles subtended by the edges of the polygon" has a very regular behavior in the interior of the polygon and a single maximum.

An Optimized Road Network

2007-01-31T03:19:00.000-08:00

Problem:
Consider a 2D region - it could be as simple as a square.

We are interested in laying out a network of roads (idealized as lines and polylines) in this region, satisfying the following requirements:

---------
0. The road network should be fully connected; there is one single network for the domain, no separate webs.

1. No point in the territory should be farther from the nearest point on *some* road by a given number 'a'. This is to ensure good penetration of the domain by the road network - no remote areas. Let us call 'a' the 'penetration constant'.

2. If A and B are two points which lie ON some roads in the network, and if we use the road network to travel from A to B, the total distance we move along the roads should not be more than the straight line distance from A to B by some given factor, say 'f' (*). This condition tries to ensure a minimum of 'intra-connectivity' in the network - it should be sufficiently cross-wired. Let us call 'f', the 'intra-connectivity factor'.

3. Yes; the road network should have the least possible total length.
---------
(*)Note: If A and B in the given region but not necessarily on the roads, we could follow the following protocol to reach B from A.
a) Find a road near to A and reach a suitable point on that road from A
b) Traverse the network of roads available optimally so that we reach B or very near B.
c) Leave the network and move to B.
A condition similar to #2 could perhaps be formulated in this case.
---------
The problem was inspired by the following question which opened the Landmark Pune Quiz 2007:
"Which Indian state has the largest length of surfaced roads?"

Update on April 5th 2007:
--------------------------
This is following some further thinking aided by a comment from Anurag.

1. It now appears that condition #3, the intra-connectivity requirement, should apply only for points on the network which are sufficiently far apart (their straight line separation should be greater than the penetration constant 'a' or 2*a). For points much less than 'a' apart, there can always be network distances 2* their straight line distance, (or sqrt(2)* straight distance) however dense the network is.

2. The road network can have open ends - especially near corners of the territory. This does not anyway spoil the connectivity.

3. It now appears that the penetration requirement can be achieved by forming *successive insets* of the boundary of the region - each successive inset is by twice the penetration distance 'a'. (Note: From the first inset of the boundary, we need to have open end roads running towards the vertices of the region until they reach a point distant a from the vertex) . Intuitively, it appears that these successive insets, suitably interconnected to ensure the intra-network connectivity would actually achieve the least lengthy network. The *suitable* interconnections might involve tricky details - but that these have to be between progressively and predictably shrinking polygons should simplify things.

Fair Partitions - III

2006-10-19T23:11:00.000-07:00

This is the third part of the present trip of partitioning *convex* polygons into equal area pieces with additional constraints.

We (Ramana Rao and self) make an attempt to solve a specific case of the larger problem - to split a triangle into 3 convex pieces with equal area and perimeter.

After this attempt, I tend to believe: if we are to partition a convex polygon into convex pieces with equal area using the *least total length of cuts*, the resulting pieces need not all be of the same perimeter (just a guess). It is well-known that if all we need are equal area pieces with least total length of cuts, the pieces need not even be convex. So, one could also wonder if insisting on the pieces having same perimeter *and* same area and also that the total length of cuts is to be minimized, we are guaranteed convex pieces.

------------------
Cutting a triangle into 3 pieces of equal area and perimeter:
------------------

Here we try to deal mainly with long and thin triangles. For reasonably 'fat' ones - those with all three angles comparable, things could be easier - for an equilateral triangle, it is trivial.
Note: Of course, my feeling is that what follows works for ALL triangles! But, even for thin triangles, I am not sure if the approach is *not an overkill*!

--------
A simple specific example or the argument:
Dividing an equilateral triangle into 3 pieces with same area and perimeter.

Let one side of the input equilateral triangle T be the base and its opposite vertex, the apex.

1. The input equilateral triangle T is initially divided into three equal area pieces with apexes meeting at the apex of T and each having base = 1/3 of the input T. Obviously the two side pieces have greater perimeter than the middle piece.

2. Slide down the apexes of the side triangles until they both reach a height 2/3 of the altitude of T. Simultaneously, increase the base of both side pieces at the expense of the middle piece until the middle piece just has one point on the base of T. ie. the bases of both the two side pieces have increased by a factor of 3/2 from their initial value. Now, it is easy to see that the areas of the three pieces (the two side pieces which are now triangles and the middle piece which is a quadrilateral) are all equal. Crucially, the middle piece now has greater perimeter than the two side pieces.

3. Note that at the initial point in the sliding, the middle piece had less perimeter and at the end, the middle piece has more perimeter. So somewhere in the middle, the perimeters all have to necessarily equal since intuitively, at every intermediate stage of the sliding process, we can have equal areas for all the three pieces - a pentagon (the middle piece) and two triangles.

This approach has not given us the obvious way to divide an equilateral triangle into three congruent isosceles triangles (which meet at the centroid of the equilateral triangle) but gives an intro to the general argument below

-------

For a general triangle.

1. Identify the shortest side of the given triangle and make it the 'base' of the triangle. The angles at the end of the base will be called base angles; the vertex opposite to the base will be called 'apex'. Note: the base perhaps need not be the shortest side, but things appear clearer with such an assignment.

Divide the base into three equal portions. Connect the ends of the three portions to the opposite vertex with lines. Now, the triangle has been divided into three equal area triangular pieces - with different perimeters (in general).

2. Now among the three pieces, identify the piece with least perimeter. This will either be (case i) the middle piece (if the two base angles are both less than 90) or (case ii)one of the end pieces (if one base angle is obtuse).

We now try to reduce the perimeters of the other two pieces while keeping the areas of all 3 pieces constant. The above two cases are treated separately. Note: In both cases, the apexes of all the three equal area pieces *initially* coincide with the apex of the input triangle.

Case (i): We increase slightly the bases of the two side pieces (these have more perimeter). This base increase is at the expense of the middle piece. Now, to keep the areas of the side pieces constant, their altitudes would have to be reduced by a greater extent. This we do by sliding the apexes of these two side pieces down along the two sides (other than the base) of the input triangle - thus converting the middle piece into a pentagon. It is clear that the perimeters of the two side pieces reduce considerably whereas the middle piece which originally had least perimeter would slightly increase its perimeter - at any rate the perimeter of the middle piece does not decrease as fast as that of the side pieces. It looks, by this process, the perimeters of all three pieces can be equalized - the result will be a two triangles and a pentagon in the middle.

Case (ii): In this case, one end piece has the largest perimeter, the middle piece will have the second largest perimeter and the other end piece will have least perimeter. We could convert the end piece with the largest perimeter into a triangle with slightly larger base and a much reduced altittude and hence perimeter - the altitude reduction will be by sliding the apex of this piece down the longest side of the input triangle. The middle piece has now become a quadrilateral. We now increase the base of the middle piece (both base increases we have done are at the expense of the base of the end piece which originally had least perimeter) and slide its highest vertex down the longest side of the input triangle. Thus the middle piece, originally an obtuse triangle, turns into a shorter and fatter quadrilateral with same area - and less perimeter. The end piece with originally least perimeter now turns into a quadrilateral with slightly narrower base but with perimeter slightly increased. The resulting pieces in this case are two quadrilaterals and a triangle.

Thus, it appears that in both cases, we can reduce the perimeter of the pieces which have more perimeter, and get the perimeters of all three pieces to equalize. I hope this exhausts all possibilities.

Generalization(?)
-----------------
And assuming the above argument is correct and complete, it also indicates how to cut a triangle into *N* pieces all with equal area and perimeter. We put N-1 equally spaced points on the base and form N equal area triangular pieces by connecting these points with the apex. Now, the perimeters of the triangles, in a left to right order either
(1) begins with a high value, steadily decreases and again increases to another maximum - this is for both base angles are less than 90 or
(2)begins with the highest (or lowest) value and steadily reduces (or increases) to a minimum (or maximum) value - when one base angle is obtuse.

Both cases, which are essentially analogous to the case (i) and (ii) treated above, appear to admit similar solutions by similar sliding of vertices. Case (i) will lead to two triangles at the ends, a pentagon in the middle containing the apex, and the rest of the pieces are quadrilaterals. Case (ii) yields a triangle at an end and all other pieces will be quadrilaterals.

The above are only plausibility arguments, not conclusive proofs. More to understand; and of course, this whole line of thinking can be demolised by a single well-aimed 'counter-punch'!

Update (October 22, 2008):
--------------------------
Some experimental work was done on the above 'sliding vertices' proposal. We tried to fair partition *right triangles* into N pieces for various N. The output is not conclusive.

For example, an isosceles right triangle with base - 10 units and along +X axis and altitude - 10 units along +Y, we could find fair partitions for up to N=10. If the base and altitude are not equal, the larger of the two could be taken as the base and we could go on for larger values of N - upto 20 and even more depending on the ratio between the sides. But evidence points to: for arbitrarily large N, merely sliding the vertices along the hypotenuse and base (with no cutlines meeting in the interior of the input triangle) might not suffice. Further work is in progress.

A specific example: base 10, altitude 10. 8 pieces required.

X coordinates of the cutline ends on the hypotenuse: 0.000000 0.095000 0.284853 0.553162 0.898463 1.335723 1.884090 2.708066

X coordinates of the cutline ends on the base: 0.000000 1.166078 2.280096 3.384029 4.506422 5.671883 6.919630 8.285777

Details of the 8 resulting pieces:

perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.207162 area: 6.250001

(the 8th piece has a slightly different perimeter. fine-tuning the position of the cutlines can achieve arbitrarily closer equality.)

'Fair Partitions' - II

2006-10-15T23:26:00.000-07:00

Here we propose a proof for a weaker version of the claim floated in the last post here: Any convex polygon, for any N, can be partitioned into N equal area and equal perimeter pieces, *if the pieces need not be convex*.

-----------------
Proof for possibility of partitioning a convex polygon into N equal area and perimeter pieces which need not themselves be convex:
-----------------
1. We first divide the input polygon into N equal area pieces so that exactly 1 'inner' piece *does not* touch the boundary and each of the remaining N -1 pieces share some *finite* boundary with this inner piece (and also divide up the outer boundary of the input polygon among them). We argue how this can always be done a little later.

2. Now, we could deform the common boundary of the inner piece with each of its N-1 neighbors to make all N-1 neighbors have the same perimeter.

If two pieces share an edge, if we introduce some zigzags (with concavities) on that edge, the perimeter of both pieces increase by the same amount - and we can do this without changing their areas. So we note among the N-1 outer pieces, which has the highest perimeter and increase the perimeters of each of the other N-2 outer pieces to this value - by tweaking the common boundary of each of them with the inner piece.

3. Now, all outer pieces have same area and same perimeter. The inner piece also has the same area but a possibly very large perimeter since its boundaries with all outer pieces (except one) have been deformed. We now try to increase the perimeter of all outer pieces to equal this large value.

We note the difference between the perimeter of the inner piece and that of an outer piece - call this quantity d. Then we deform *all* the boundaries between the outer pieces - ie the dividing boundary between outer piece 1 and 2, then the boundary between 2 and 3 and so on - so that the increase in perimeter to both the pieces separated by a given boundary is d/2. So, when all boundaries have been deformed, every outer piece increases its perimeter by d - their areas should be kept constant - which is as desired.

Exception: If after step 2, the inner piece still has *less perimeter* than the common value of the perimeters of the outer pieces, we could tweak the boundary of the input piece with each of the outer ones equally so that every outer piece gains a little perimeter and the innter piece gains N-1 times that much so we could again equalize the perimeters.

A bit remains: how to divide the input convex polygon into N equal area pieces so that one piece is in the middle and the remaining N-1 surround it? For this, we could scale the input polygon by a factor of N and the resulting small polygon can be put somewhere inside the input polygon (this scaling will work if the input polygon is convex). This is the central piece. Then we can walk around the central piece and sweep out N-1 equal area pieces from the remaining 'annular' portion of the input polygon. These N-1 outer pieces are free to be be concave so we could force each of these to share a finite boundary with the inner piece.

Remarks:
-------

Obviously, this approach can cause all the pieces to have very large perimeters and they will also have jagged boundaries. No attempt has been made to minimize the sum of the perimeters of the pieces, which remains to be understood.

We can't see how this argument can be modified to handle the case where the pieces have also to be convex. But this argument does appear to allow us to prove this: "for any N, any (non-convex) polygon can be broken into (non-convex) N pieces all of equal area and perimeter" - the only new idea is to put an thinned down - almost insetted - polygon of area 1/N of the target polygon in the interior of the target (the thinned polygon will be of the same basic skeletal shape as the target and much thinner and will run along the entire length of the target; intuitively, such a polygon can always be found with the required area) - This skeletal polygon will serve as the central polygon in the above proof. The rest of the proof should go thru unchanged. Of course, now we have the question: how to partition a general polygon into general pieces of equal area and equal perimeter *minimizing the perimeter of each*?

---------
For the case when the pieces also have to be convex (the full version of the claim), we tried to find counter-examples like 'dividing a triangle into 5 convex pieces with equal area and perimeter' - no progress yet on that front.

'Fair' Partitions

2006-09-28T06:57:00.000-07:00

Let us (N. Ramana Rao and self) float yet another geometric conjecture

****
Given any convex shape and any positive integer N. There exist some way(s) of partitioning this shape into N convex pieces so that all pieces have equal area and equal perimeter.
****

Note: We could define the 'fair partition' of a polygon as a partition into pieces of equal area and perimeter and further, a 'convex fair partition' as a fair partition in which the pieces are also convex. The claim above could be restated as: "for any N, any convex shape allows convex fair partitioning into N pieces".

If the claim is indeed true, how could one try to minimize the perimeter of each resulting piece?.

To be honest I don't know for sure if it is possible to divide, say, an equilateral triangle into, say, 5 convex pieces all with same area and same perimeter. Even this simple example appears somewhat tricky although the convexity requirement on the pieces is a strong constraint which makes the claim shaky.

Of course, if the claim gets successfully countered, then, one could relax the claim in various ways and say, say

(1) any convex shape, for any N, can be cut into N pieces, not necessarily convex so that all pieces have same area and same perimeter (this claim looks very plausible as of now).

or else

(2) For any convex shape, there exists some N, so that the shape can be cut into N convex pieces of same area and same perimeter. Perhaps one could say: "some N greater than 2". Well, things seem murky!

I could not find any known result on this - although there has been work on dividing into pieces so that every piece has same area and the same fraction of the outer boundary of the target. The requirement that all pieces should have same perimeter is not very easy to ensure - at least not as easy as ensuring equal areas for them. One does not know ab initio what precise perimeter each piece should have!

Traversing A Tree

2006-06-22T03:16:00.000-07:00

Problem:

Given a Binary Tree. You have to print the data in inorder traversal.
Restrictions: No recursion, no queue, no stack, no extra memory...

Suggested Solution:

One could use a single additional integer N to hold the path to nodes in the input tree - the number's binary equivalent will signify a path from root to some element: the first bit in the binary string stands of root; then for each successive bit, if bit is 0, move to the left child of the current element and if the bit is 1 move to the right child. For instance the value of N=9 with binary string 1001 signifies the path to the node reached from root (the first 1 in the binary) by a left-left-right (0-0-1)path from root. The mapping from the value of this number N and elements in the input tree is one-one.

For in-order traversal, one could find the next element at each step as follows. We maintain throughout a single integer whose binary representation gives the path from root to the current element in the traversal. This binary string keeps getting bits added or removed from it as we progress. Appending a 1 to the binary string implies multiplying the integer by 2 and adding 1; deleting a 0 at the end, corresponds to dividing the integer by 2 and so on.

The traversal begins at the left most element of the input tree (need not be a leaf) - got by starting with a binary string with a single 1 and adding as many 0's to it as allowed by the input tree.

Cases:
1: If you are currently at a leaf at the end of a leftward going branch, the next element in traversal is its parent. this parent is reached by dropping a 0 from the end of the binary string (path) to the current element.

2. If you are at a leaf at the end of a right going branch, the next inorder element is got by backtracking up to its nearest ancestor A which is the left child of some other node, say P and return P. This can be done by dropping 1's from the end of the binary string corresponding to current element till a 0 is reached and then dropping one 0.

3. If you are at any other element, the next element in the traversal is the left most leaf element of the right subtree starting at the current element. This next element can be reached by the following process:
If possible append a 1 to the binary string. Append as many 0's as possible - if corresponding nodes exist in the input tree. Wherever no more 0 can be appended, stop and return that element. If no 1 can be appended at the beginning, the current element, though not a leaf ought to be treated as a leaf. If the present last bit of the binary number is 1, execute case 2. if the last bit is 0, execute case 1.

The traversal ends when one finds oneself at the root on dropping a 1 from the binary string.

Thus we seem to have carried out the in-order traversal using only a single extra integer.

A Sequence Puzzle

2006-05-17T05:01:00.000-07:00

The following problem was contributed by B. Sairam.

There is a series which goes like this

T(1) = 1
T(2) = 2
T(k) = T(k-1) + SumOfDigitsOf ( T(k-1) ). For instance, if T(p) = 129 then
T(p+1) = 129+1+2+9

Question: Then does the number 123456789 occur in this series?

Spoiler Warning: Solution below!

[Additional questions: How fast does the function digitsum(N) grow as a function of N? How fast does the therm T(N) in the above series grow with N?]

-----------

-----------
Of course, it is easy to check programmatically that 123456789 does not occur in the series. A non-brute-force argument follows....
-----------

Every number N and digitsum(N) both have the same value modulo 3.

When a number that equals 1 (modulo 3) is added to its own digitsum, the value of the sum (modulo 3) will be 2.

When a number that equals 2 (modulo 3) is added to its own digitsum, the value of the sum (modulo 3) will be 1.

The series begins with 1, which equals 1 (modulo 3). the next will be 2, which equals 2 (modulo 3). The next number is 4 which equals 1 (modulo 3) the next number will equal 2 (modulo 3) and so on...

Thus,the series consists alternately of numbers equaling 1 and 2 modulo 3. But the given number equals 0 modulo 3 (since it can be easily checked it is divisible by 3). so, it cannot be in the series. QED.

A 'Road Coloring' Problem

2006-04-13T10:12:00.000-07:00

This is on the July 2003 challenge at the Ponder This column at IBM Research. See here for the statement of the problem.

This problem is stated to be still open. Here we (N. Ramana Rao and self)look at a special case thereof.

1. We look at the special case of Road Coloring where at least one of the cities has an outgoing road ending in the same city. Suppose there are N cities, and Cx be any of the cities which have road to itself. We do the following visualization:

Keep Cx at the center and arrange the other cities in layers around it. First keep those cities which have roads directly leading to Cx to Cx in the first layer around Cx. Call this layer L1. Now keep the cities which have roads directly leading to cities of L1 in the next layer L2. Thus we keep all the cities in layers around Cx.

The coloring:
For every other city C, there is at least one outgoing road leading into the layer just inside of the layer on which C lies. Color this road from C to its next inner layer red. The other outgoing road from C is colored green. If both roads from C lead to the next inner layer, either may be colored red or green. For the central city Cx, the self-reaching loop road should be red.

With this coloring, one has a constant and finite path leading from ANY city to the central city Cx. This sequence of roads to the central city is always of the form of one Green followed by as many Reds as there are layers (an example is given below).

For any specified city C', there exists a fixed path from central city Cx to it (guaranteed in problem statement). So given any destination C', starting at any unknown source C, we can by first taking the constant path to the center and the path from center to C'. The path will be the same for any starting city C and will depend only on destination C'.

Example:

There are 5 cities numbered 1 to 5. arranged in a pentagon and connected clockwise. 1, 2, 4 and 5 have one road each that loops back on itself. 3-5 is another road.

ie, the roads are 1-2, 2-3, 3-4, 4-5, 5-1, 1-1, 2-2, 3-5, 4-4, 5-5

there are two cycles 1-2-3-5 (length 4) and 1-2-3-4-5 (length 5) - the lengths are relatively prime. As far as we can make out, this property is not used in what follows...

We choose 1 as the central city. The next layer has only 5 (since only from 5 is there a direct path to 1) In the next layer there are two cities, 3 and 4 In the outermost layer there is only 2.

By above coloring scheme, 2-3, 3-5, 4-5, 5-1, and 1-1 should be red and the others roads are green.

The seqeunce GRRR takes you to city 1 from any starting city. Once we have a samepath to the central city from anywhere we also have a same path to any required destination from anywhere.

A 'Line Fitting' Problem

2006-04-13T09:34:00.000-07:00

This post came out of a discussion with N. Ramana Rao.

Statement of the Problem:
------------------------
Given a distribution of N points in 2D Euclidean plane. Describe the line which minimizes the Sum of the Orthogonal Distances of the given points from itself.

Please note that we consider abs values of the perpendicular distances themselves, NOT their squares. We could call such a line a "min-SOD line" o r perhaps the "spine" of the point distribution. The line need not be unique.

An Extension: If we are to minimize (the SOD plus the minimum length of the line so that it contains the feet of the perpendiculars from all the input points to the min-SOD line) what could be said about a line that achieves it?

Proposed answer to the main part:
--------------------------------

(This is a 'lemma' which we have tried to use to find an efficient algorithm to compute the min-SOD line).

A min-SOD line (spine) has to pass thru at least two of the input points and should be such that on neither half plane it divides the plane into, there should be more than Floor (N/2) points.

Attempted proof of our lemma:
------------------------------

Consider a line which claims to be the spine and which pass thru none of the N input points. First we note that candidate line has to have equal number of the input points on either side ( else we could shift in parallel to itself in one of the two possible directions and achieve a reduction in SOD).

Let this candidate spine be infinitesimally rotated in the plane about ANY point on itself, say P. Now, for any input point Pi the perpendicular
distance from the candidate spine thru P is given by r* sin t where t is the angle made by the line from P to Pi and the candidate spine . When the line rotates infinitesimally by angle dt, the differential change in the perpendicular distance is r* cos t dt.

We note that if the line were to rotate in the opposite direction from what considered above, the differential change in the perpendicular distance of the point Pi from the candidate spine would simply change sign (because then dt -> -dt ).

So for the entire set of input points, the overall change in the Sum of Orthogonal Distances will also have opposite signs when the candidate spine is rotated in the two possible directions.

This proves that if SOD increases in one direction overall, it necessarily decreases in the other direction - it cannot increase in both directions => the position of the candidate spine is not a minimum for the SOD. However if the candidate line passes thru one of the input points, for that point the perpendicular distance increases in both directions of rotation and then the line COULD BE be one for which the SOD is a minimum.

Special case:
------------
The SOD could be unchanged for both infinitesimal rotations (for example if the input points are arranged along two parallel lines in equal numbers and the candidate spine is parallel to both these lines and equidistant from both). Then we note that this property of unchanging SOD holds only locally and gets lost the moment the we disturb the symmetry of the distribution of the input points about the candidate spine by an infinitesimal rotation of the candidate spine. This always seems to be the case as long as the input points are a discrete set.

Thus we see that the candidate spine has to pass thru at least one input point. We now repeat the above argument with this input point as the center of rotation for the candidate spine; we see that the candidate line has to pass thru one more input point.

We thus conclude that the spine passes thru at least two input points and neither side it has more than floor (N/2) points.

Remarks on computing the spine:
------------------------------
For input points in general position, the spine is one of the Halving lines. So in order to computationally determine the spine for a given point set, we could try to find all the halving lines and compare the Sum of Orthogonal Distances (SOD) of the input points from each halving line.

From the work of Tamal Dey and others on the 'k-set problem', the number of halving lines for N points could be as high as N^4/3. Finding them all could take O(log N) time per halving line using dynamic convex hull data structures. Finding the SOD for one halving line and to recalculate it for each successive halving line could take only constant time per iteration. Thus we could have approximately an O(N^4/3 * log N) algorithm to find the spine. We are grateful to Prof. David Eppstein (UC -Irvine) for pointing out these details to us.

We are not aware of better complexity results for this problem. We also do not know if this problem has been explored before.

The extension:
---------
If we are to minimize {the SOD plus the minimum length of the spine so that it just contains the feet of the perpendiculars from all the input points to the min-SOD line} , the spine again appears to satisfy the above property - it passes thru at least two input points and has <= floor(N/2) points on either side. the same arguments appear to hold.

However, the line that minizes only the SOD and the line minimizing {SOD + 'spine length'} need not be the same. For example, if there are 3 input points at the vertices of an isosceles right triangle, the min-SOD line is the hypotenuse but if we are to minimize the SOD + spine length, we choose either of the two equal sides of the triangle as the spine.

Additional Remark:
------------------

It would seem that the lemma could be improved to at most Floor( (N-1)/2) points on each side of the line. This makes a difference when N is even.

Suppose N is even and we have a line L passing through at least 2 points, with exactly N/2 points on one side. Shift L parallel to itself towards the N/2 points (which does not change the SOD), so it is not touching any points. Suppose L is now the x-axis. Rotate it through theta around the origin.

(Remark: because there are exactly N/2 points on each side, it doesn't matter which point we choose as pivot.)

If there were N/2 points (x_i,y_i) above the axis and N/2 points (z_j, - w_j) below the axis (notice y_i and w_j are all positive), then the SOD (as a function of theta) is ( sum y_i + sum w_j) (cos theta) + ( - sum x_i + sum z_j) (sin theta). The second derivative at theta=0 is ( - sum y_i - sum w_j ) which is negative, so a small rotation in one direction or the other will decrease SOD. So we did not have the minimum. Conclusion: at most Floor((N-1)/2) points on each side of the line.

Note:
-----
For a distribution of points in Euclidean 3D, the min-SOD line NEED NOT pass thru any of the points.

Packing Circles - Questions Galore!

2006-04-13T09:13:00.000-07:00

The prime inspiration for this post is 'Erich's Packing Center'. What I have here is a long list of doubts based on the interesting facts given there on the specific problem of packing circles in squares - for a given number N, finding the smallest square which will hold exactly N unit circles. For several examples please see here .

1. It appears that one needs to solve each instance of the problem (each instance given by a certain specified number of circles to be packed in a least square) separately. Are there general rules for characterizing packings like: (i) For what numbers could we always manage with a simple parallelogram lattice of circles (as in the case of 16, 18 and 20 circles for instance) ? (ii) For what numbers will there be one or more 'loose circles' in the packing (circles which can move a finite distance about its position in the packing without violating the square) (7, 11, 17, 21 etc..) ?

Remark: It appears that there are no such rules. Obviously some numbers work well for this 18=4+3+4+3+4 and 20=4+4+4+4+4. But you don't know ahead of time that this translates into an optimal packing.

2. If we allow only simple parallelogram lattices of circles (with one circle per 'unit cell') to be used while packing circles in squares, could we have a general method to find the minimal square given the number of circles to be packed? This becomes relevant if we are automating the packing and can only handle simple lattice arrangements of the circles.

Remark: The hex packing is a lot better than the diamond packing, so for large N this won't be as good - it would be better to place the square over a hex lattice and trap as many circles as possible.

3. If we allow only simple parallelogram lattices but allow the container to be a rectangle with (i) minimum area or (ii) minimum perimeter, do we have a single general algorithm for any number of circles to be packed?

Remark: It appears this is unexplored territory.

4. And if we allow the container to be other than a square, can the 'loose circles' /non-lattice arrangements be always avoided for some specific type of container? Even in the 'Circles in Circles' page at the 'Packing Center', loose circles are seen for some numbers.

Remark: "thin" enough containers won't have this problem, But it is hard to see any shape that won't have this problem when scaled up large enough.

5. It is possible that there is a connection between selections of N circles from a fixed lattice to polyominoes with N squares - the number of different N-ominoes is exponential. The number of candidate circle arrangements perhaps is probably exponential as well.

Maybe we could have ways to filter down the number of candidate selections of circles to a polynomial in N - perhaps by eliminating circle selections corresponding to long 'polyominoes' if one is looking for the smallest square.

Remark: One needs to find a good way to prune the tree of polyominoes to only consider ones that are fat instead of skinny. Perhaps a more general idea of convexity, while making sure the width and height don't differ by 2 or more..

6. I would also like to know if there are any problems in this area which are known to be NP-complete. Finding the minimal square for a given number of circles seems to be far more complex than NP-complete since one cannot choose from a discrete set of options.

8. Here is an apparently simpler problem: Given a known and fixed parallelogram lattice of circles and a number N. Find the minimal area/ perimeter rectangle (or square) that can be placed on the lattice so that it 'traps' N circles fully within it. Does this or some other variant of the main packing problem enable a reduction of the problem to choosing from a discrete set of candidates?

Remark: One needs to see how to reduce the problem to finitely many cases.

Starting Up...

2006-04-12T09:33:00.000-07:00

Hello World!

This blog is a spinoff from my 'catch all' collection of personal stuff, 'Anamika' . Here I will try to post as regularly as possible on matters geometric, computational etc..

This initial post is a 'recap'. Let me form here, a 'bucket' of pointers to some selected posts made at Anamika over the last year.

1. On the 'Change Making' problem

2. A problem on Calibrating Glass Bulbs

3. Solution to the Glass Bulb Problem

4. On Partitioning Polygons

5. A Puzzle on Prisoners and Switches

6. More on the Prisoners and Switches Puzzle

7. An encounter with Sudoku

8. A Pigeon Hole Puzzle

9. Speculations on the Angel Problem

10. 'Atomic' Polygons

11. A 'Conjecture'

12. A Conjecture Debunked

13. Cutting Polygons - contd.