"Best" Division Of Square Into 3 Parts
Leroy Quet
I am wondering what is the "best" way to divide this square into 3
equal-area, but not necessarily equally shaped, pieces.
By "'best' way", I mean that the sum of the 3 maximum "diameters" of
the pieces is minimized. By "diameter" I mean, as is what I think is
the usual definition of the general sense of this word, the maximum
(maximum, in the case of this question) distance between 2 parallel
lines that the piece can fit between, the perimeter of the piece
touching both lines (but crossing neither line).
The legal fine-print:
The pieces are to be simply-connected (as I understand the term), but
not necessarily convex.
And each piece has an area of 1/3, and has no area intersecting with
any other piece.
The problem can most-likely be described in much more friendly and
understandable terms. I hope that, not only is the above clear, but
that I did not confuse the matter with an incomplete discription of
the problem or with ambiguous language.
This must be a well-known problem. What about generalizing it to
n-pieces?
As an example, for 4=n, if we simply divide the square, with two
perpendicular lines that each bisect the square, into four identical
squares, the smaller squares each have a maximum-diameter of
squareroot(1/2). So the sum of these maximum-diameters is sqrt(8).
Intuitively to me, this seems like a minimization of the sum of
diameters. If we had instead divided the square into 4 equal triangles
by connecting diametrically-opposed vertexes, each diameter would be 1
(measured along the triangles' hypotenuses=the square's edge). So this
division would not be the solution for n=4, since
4 > sqrt(8).
Thanks,
Leroy Quet
David W. Cantrell
> Start with a square with side-length 1.
>
> I am wondering what is the "best" way to divide this square into 3
> equal-area, but not necessarily equally shaped, pieces.
>
> By "'best' way", I mean that the sum of the 3 maximum "diameters" of
> the pieces is minimized. By "diameter" I mean, as is what I think is
> the usual definition of the general sense of this word, the maximum
> (maximum, in the case of this question) distance between 2 parallel
> lines that the piece can fit between, the perimeter of the piece
> touching both lines (but crossing neither line).
>
> The legal fine-print:
> The pieces are to be simply-connected (as I understand the term), but
> not necessarily convex.
> And each piece has an area of 1/3, and has no area intersecting with
> any other piece.
>
> The problem can most-likely be described in much more friendly and
> understandable terms. I hope that, not only is the above clear, but
> that I did not confuse the matter with an incomplete discription of
> the problem or with ambiguous language.
>
> This must be a well-known problem.
Perhaps, although I don't remember having seen it before.
Just as a start, let me note that there is a trivial division of the square
into three rectangles -- two of which are 2/3 by 1/2, the other 1 by 1/3 --
giving (5 + Sqrt(10))/3, which is about 2.72, for the sum of the diameters.
I wonder if that is close to the desired minimum.
David
Gerry Myerson
David W. Cantrell <DWCan...@sigmaxi.org> wrote:
> qqq...@mindspring.com (Leroy Quet) wrote:
> > Start with a square with side-length 1.
> >
> > I am wondering what is the "best" way to divide this square into 3
> > equal-area, but not necessarily equally shaped, pieces.
> >
> > By "'best' way", I mean that the sum of the 3 maximum "diameters" of
> > the pieces is minimized. By "diameter" I mean, as is what I think is
> > the usual definition of the general sense of this word, the maximum
> > (maximum, in the case of this question) distance between 2 parallel
> > lines that the piece can fit between, the perimeter of the piece
> > touching both lines (but crossing neither line).
> >
> > The legal fine-print:
> > The pieces are to be simply-connected (as I understand the term), but
> > not necessarily convex.
> > And each piece has an area of 1/3, and has no area intersecting with
> > any other piece.
> > This must be a well-known problem.
>
> Perhaps, although I don't remember having seen it before.
>
> Just as a start, let me note that there is a trivial division of the square
> into three rectangles -- two of which are 2/3 by 1/2, the other 1 by 1/3 --
> giving (5 + Sqrt(10))/3, which is about 2.72, for the sum of the diameters.
> I wonder if that is close to the desired minimum.
There was something like this in Steinhaus, Mathematical Snapshots,
pages 50-51 (last topic in Chapter 2). Three cowboys have to watch
a herd of cattle in a square pasture & have to divide the square
up in some equitable way. Have a look, see if it's useful.
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
Patrick Hamlyn
>By "'best' way", I mean that the sum of the 3 maximum "diameters" of
>the pieces is minimized. By "diameter" I mean, as is what I think is
>the usual definition of the general sense of this word, the maximum
>(maximum, in the case of this question) distance between 2 parallel
>lines that the piece can fit between, the perimeter of the piece
>touching both lines (but crossing neither line).
It might be useful also to look at minimising instead the total perimeter of all
three pieces, or alternatively minimise the biggest perimeter. This is the
commonest measure of convexity, if convexity is what you are aiming for.
I would think a shape something like this might work:
-------------------
| |
|. .|
| . . |
| . . |
| . . |
| . |
| . |
| . |
| . |
-------------------
Losing the left-right symmetry might help too.
--
Patrick Hamlyn posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere
Moderator: polyforms group (polyforms...@egroups.com)
Martin DeMello
> qqq...@mindspring.com (Leroy Quet) wrote:
>
>>By "'best' way", I mean that the sum of the 3 maximum "diameters" of
>>the pieces is minimized. By "diameter" I mean, as is what I think is
>>the usual definition of the general sense of this word, the maximum
>>(maximum, in the case of this question) distance between 2 parallel
>>lines that the piece can fit between, the perimeter of the piece
>>touching both lines (but crossing neither line).
>
> It might be useful also to look at minimising instead the total
> perimeter of all three pieces, or alternatively minimise the biggest
> perimeter. This is the commonest measure of convexity, if convexity is
> what you are aiming for.
You could also minimise the largest diameter, if what you're after is
an (ill-defined but nonetheless real) solution that "feels satisfyingly
minimal". It'd be interesting to visually compare various solutions and
see which looked better.
martin
Fred the Wonder Worm
In article <wTMQa.9824$xn5.1...@news0.telusplanet.net>,
Martin DeMello <martin...@yahoo.com> wrote:
>
> You could also minimise the largest diameter, if what you're after is
> an (ill-defined but nonetheless real) solution that "feels satisfyingly
> minimal". It'd be interesting to visually compare various solutions and
> see which looked better.
It is fairly straightforward to show that the smallest largest diameter
possible is Sqrt(65)/8. Using an 8x8 square to keep things nice and
integral, one can achieve this with two 4x7 rectangles and one 1x8
rectangle. To ensure that they all have the same area one needs to
scoop out part of the bigger rectangles and add it to the smaller one.
One way to do this is to join a (10/3)x4 rectangle to the 1x8 in the
"obvious" manner.
A more visually pleasing picture would use a circular arc to augment
the rectangle, with radius approximately 6.69+.
Cheers,
Geoff.
-----------------------------------------------------------------------------
Geoff Bailey (Fred the Wonder Worm) | Programmer by trade --
ft...@maths.usyd.edu.au | Gameplayer by vocation.
-----------------------------------------------------------------------------
O.H.
Gnomonical arrangement?
http://www.gvdnet.dk/~hagen/combies.htm
Regards
Hagen
Ed Murphy
> Perhaps I can furnish some assistance to the problem by this
> Gnomonical arrangement?
> http://www.gvdnet.dk/~hagen/combies.htm
This seems to involve dividing a square into sections, based partly on
geometric properties and partly on some sort of linguistic content. It
doesn't seem to bear much relation to Leroy's original problem, which
involves dividing a square into sections based solely on geometric
properties.
Hugo Pfoertner
>
> Start with a square with side-length 1.
>
> I am wondering what is the "best" way to divide this square into 3
> equal-area, but not necessarily equally shaped, pieces.
>
> This must be a well-known problem. What about generalizing it to
> n-pieces?
>
>
> Thanks,
> Leroy Quet
For larger n it might be possible to start with
"The best known packings of equal circles in the unit square"
http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html
or with
Triangles in Squares: http://www.stetson.edu/~efriedma/triinsqu/
Squares in Squares: http://www.stetson.edu/~efriedma/squinsqu/
Rectangles in Squares: http://www.stetson.edu/~efriedma/recanima/
Hugo Pfoertner
Jim Ferry
> Start with a square with side-length 1.
>
> I am wondering what is the "best" way to divide this square into 3
> equal-area, but not necessarily equally shaped, pieces.
>
> By "'best' way", I mean that the sum of the 3 maximum "diameters" of
> the pieces is minimized. By "diameter" I mean, as is what I think is
> the usual definition of the general sense of this word, the maximum
> (maximum, in the case of this question) distance between 2 parallel
> lines that the piece can fit between, the perimeter of the piece
> touching both lines (but crossing neither line).
>
>
> The legal fine-print:
> The pieces are to be simply-connected (as I understand the term), but
> not necessarily convex.
> And each piece has an area of 1/3, and has no area intersecting with
> any other piece.
David W. Cantrell wrote:
> Just as a start, let me note that there is a trivial division of the square
> into three rectangles -- two of which are 2/3 by 1/2, the other 1 by 1/3 --
> giving (5 + Sqrt(10))/3, which is about 2.72, for the sum of the diameters.
> I wonder if that is close to the desired minimum.
I found a configuration that yields a diameter sum of about 2.62. I think
that it might be optimal, but I haven't attempted a proof.
Start with a configuration like David's: two rectangles (R1 and R2) which are
x by 1/2, and another (R3) which is 1-x by 1. The diameter of R1 (and of R2) is
d = sqrt(x^2 + 1/4), whereas the diameter of R3 is sqrt(1 + (1-x)^2).
We now augment R1 at the expense of R3 by sweeping out arcs of radius d (as in
the construction of the Reuleaux triangle: see, for example,
http://mathworld.wolfram.com/ReuleauxTriangle.html). We write R1 as ABCD, with
C and D lying on R3. Let E be the point inside R3 which is a distance d from A
and from B. Now augment R1 by the region swept out by two arcs: the first
centered at A and sweeping from C to E, and the second centered at B and sweeping
from E to D.
Let's compute the area of the augmented R1. This area consists of the original
area of the rectangle (x/2), plus that of a triangle ((sqrt(d^2 - 1/16) - x)/4),
plus those of two circular segments. We let t be the angle swept by the arc CE
(or by ED). Then t = arcCos(1/(4d)) - arcCos(1/(2d)). The area of each circular
segment is then (d^2/2) (t - sin(t)).
Therefore the area of the augmented R1 is d^2 (t - sin(t)) + (sqrt(d^2 - 1/4) +
sqrt(d^2 - 1/16)) / 4, which simplifies to
area = d^2 (arcSec(4d) - arcSec(2d)) + sqrt(d^2 - 1/4)/2 - sqrt(d^2 - 1/16)/4.
We augment R2 in the same way. Setting the above area to 1/3 yields the value
d = 0.76939464710029495196.
The sum of the three diameters is s = 2d + sqrt(1 + (1 - sqrt(d^2 - 1/4))^2), or
s = 2.6215668851316829777.
--
| Jim Ferry | Center for Simulation |
+------------------------------------+ of Advanced Rockets |
| http://www.uiuc.edu/ph/www/jferry/ +------------------------+
| jferry@[delete_this]uiuc.edu | University of Illinois |
Leroy Quet
How about if we restrict the pieces to being formed by taking the
square and making only 3 straight cuts, each from one of three points
on the square's perimeter to a single point in the square's interior?
It seems that, under this restriction, the optimal solution might be
more easily findable, either analytically or numerically (using a
computer).
Am I correct in assuming that if we take 3 points on the square's
perimeter, then there is at-most (if any such point exists) one
interior point which would subdivide the square into 3 equal-area
pieces?
Thank you,
Leroy Quet
ant...@gmail.com
> By "'best' way", I mean that the sum of the 3 maximum "diameters" of
> the pieces is minimized. By "diameter" I mean, as is what I think is
> the usual definition of the general sense of this word, the maximum
> (maximum, in the case of this question) distance between 2 parallel
> lines that the piece can fit between, the perimeter of the piece
> touching both lines (but crossing neither line).
ant...@gmail.com
> Though it has different initial formulation, it is proved exact solution, so it can help in your problem too.