All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Slice a Circle to fit a Rectangle (Posted on 2007-08-22)
The goal of this problem is to slice a unit circle into two pieces which can be fit into a rectangle of minimal area.
Consider these three methods:

One: Slice the circle across its diameter and slide the pieces along each other a little.
What distance between the radii of the two semicircles gives the smallest rectangle? This rectangle has a smaller area than square that circumscribes the original circle. What is the ratio of rectangle to square?

Two: Slice the circle along a diameter and place these into a rectangle so the straight edges of each semicircle are along opposite edges of the rectangle.
What is the ratio of rectangle to square this time?

Three: Slice a segment off of the circle and place this segment to the side. The large piece's straight edge is along one side of the rectangle. The straight edge of the segment is tangent to the large piece but not necessarily parallel to a side of the rectangle.
What chord length minimizes the rectangle? What is the ratio?

Note: Part Three is may be particularly difficult to find an exact solution for. If you have a method of finding a good approximation feel free to share your results.

 No Solution Yet Submitted by Jer Rating: 4.1667 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer exploration of part 3 | Comment 5 of 10 |

There are quite a few complexities in calculating the resulting rectangular area, and it is quite prone to error. So the derivation below should be checked, as well as the coding to see it matches the derivation. I've done my checking, but other eyes might see more.

Let the segment be sliced off the left side, for sake of argument. Let x be the width of the thickest part (middle) of the segment and theta be half the angle at the circle's center subtended by the segment.

theta = arccos(1-x)

Let alpha be the angle clockwise from the top of the circle, where the flat portion of the segment will be placed tangent to the circle.  We'll assume this will be no larger than 90, as we whatever could be placed on bottom could be placed on top instead. In the negative direction, it can't go any further than where it would go outside the left side of the rectangle as determined by where the circle was cut off.

The center of the arc of the segment so placed will be at (x*sin(alpha),x*cos(alpha)); it still retains its radius of curvature of 1.

If |alpha| exceeds theta, the height of the rectangle will be determined by the height of an endpoint of the segment, and is 1 + cos(alpha) + |sin(theta)*sin(alpha)|, using the absolute value as the opposite end of the segment will be determinative for positive or negative alpha. The 1 at the beginning is the bottom radius of the circle.

If, on the other hand, theta exceeds |alpha|, the highest point will be along the arc of the segment. The high point is then at 1 + 1 + yc, where yc is the x*cos(alpha) y-coordinate of the center of curvature of the arc portion of the segment.

In no instance, however, can the height be less than 2, which is the height if |alpha| is so large that no part of the segment extends above the top of the circle.

The width is done similarly, generally with sin(alpha) and cos(alpha) switched. But a check has to be made to see that the portion of the circle to the left of the slice is not exceeded.

The following program produces a table, and a summary of the best value (least area) found. The lowAlpha, highAlpha, lowX and highX are in their final states after homing in on a minimum.

DECLARE FUNCTION acos# (x#)
DEFDBL A-Z
DIM SHARED pi
pi = ATN(1) * 4

CLS

min = 999
lowAlpha = 12.03875#: highAlpha = 12.03876#: stSize = (highAlpha - lowAlpha) / 36#: highAlpha = highAlpha + stSize / 4
lowX = .4124#: highX = .4126#: xStep = (highX - lowX) / 8#: highX = highX + xStep / 4
FOR alpha = lowAlpha TO highAlpha STEP stSize
LOCATE 2 + (alpha - lowAlpha) / stSize, 1
PRINT USING "###.#### "; alpha;
FOR x = lowX TO highX STEP xStep
LOCATE 1, INT((x - lowX) / xStep + 1.5) * 7 + 2
PRINT USING " #.####"; x;
theta = acos(1 - x)
sc = SIN(theta)
cx = x * SIN(alpha * pi / 180)
cy = x * COS(alpha * pi / 180)
IF ABS(alpha * pi / 180) > theta THEN
h = 1 + COS(alpha * pi / 180) + ABS(sc * SIN(alpha * pi / 180))
ELSE
h = 1 + cy + 1
END IF
IF h < 2 THEN h = 2

IF (90 - ABS(alpha)) * pi / 180 > theta THEN
exW = ABS(SIN(alpha * pi / 180)) + sc * COS(alpha * pi / 180)
ELSE
exW = ABS(cx) + 1
END IF
exW2 = SIN(alpha * pi / 180) - sc * COS(alpha * pi / 180)
IF exW > (1 - x) AND alpha < 0 OR -exW2 > (1 - x) AND alpha >= 0 THEN
' doesn't work; extends beyond left slice
ELSE
IF alpha < 0 THEN
w = 2 - x
ELSE
IF exW < 1 THEN exW = 1
w = 1 - x + exW
END IF
LOCATE 2 + (alpha - lowAlpha) / stSize, INT((x - lowX) / xStep + 1.5) * 7 + 2
PRINT USING "##.####"; w * h
IF w * h < min THEN
min = w * h: minAlpha = alpha: minX = x
mincx = cx: mincy = cy
minw = w: minh = h: mintheta = theta * 180 / pi
END IF
END IF

NEXT
NEXT
LOCATE 45, 1: PRINT min, minAlpha, minX
PRINT mincx, mincy
PRINT minw, minh, mintheta

FUNCTION acos (x)
IF ABS(x) = 1 THEN
a = pi / 2 - pi / 2 * (SGN(x))
ELSEIF x = 0 THEN
a = pi / 2
ELSE
a = ATN(SQR(1 - x * x) / x)
END IF
acos = a
END FUNCTION

producing

`            x: 0.0500 0.1000 0.1500 0.2000 0.2500 0.3000 0.3500 0.4000 0.4500alpha   -90.0000-85.0000-80.0000-75.0000-70.0000-65.0000-60.0000-55.0000-50.0000-45.0000 3.9000-40.0000 3.9000-35.0000 3.9000-30.0000 3.9432 3.9595-25.0000 3.9746 3.9722-20.0000 3.9907 3.9785 3.9608-15.0000 3.9942 3.9835 3.9680-10.0000 3.9960 3.9871 3.9733 3.9545 -5.0000 3.9971 3.9893 3.9764 3.9586 3.9358  0.0000 3.9975 3.9900 3.9775 3.9600 3.9375  5.0000 3.9971 3.9893 3.9764 3.9586 3.9358 3.9081 10.0000 3.9960 3.9871 3.9733 3.9545 3.9309 3.9023 3.8687 15.0000 3.9942 3.9835 3.9680 3.9477 3.9226 3.8926 3.8578 3.8935 3.9333 20.0000 3.9907 3.9785 3.9608 3.9383 3.9111 3.9091 3.9734 4.0242 4.0627 25.0000 3.9746 3.9722 3.9515 3.9263 3.9457 4.0209 4.0814 4.1289 4.1644 30.0000 3.9432 3.9595 3.9403 3.9544 4.0403 4.1094 4.1643 4.2067 4.2376 35.0000 3.9000 3.9314 3.9352 4.0357 4.1128 4.1739 4.2214 4.2571 4.2827 40.0000 3.9000 3.8878 3.9911 4.0935 4.1627 4.2140 4.2526 4.2833 4.3125 45.0000 3.9000 3.8600 4.0128 4.1165 4.1861 4.2299 4.2646 4.2982 4.3309 50.0000 3.9000 3.8925 3.9999 4.1033 4.1732 4.2260 4.2677 4.3030 4.3375 55.0000 3.9000 3.9383 3.9526 4.0554 4.1351 4.2000 4.2532 4.2966 4.3325 60.0000 3.9443 3.9679 3.9598 3.9851 4.0762 4.1518 4.2150 4.2681 4.3125 65.0000 3.9765 3.9813 3.9719 3.9625 3.9968 4.0815 4.1535 4.2148 4.2672 70.0000 3.9930 3.9879 3.9819 3.9759 3.9698 3.9898 4.0688 4.1370 4.1959 75.0000 3.9966 3.9932 3.9898 3.9864 3.9830 3.9796 3.9761 4.0354 4.0994 80.0000 3.9985 3.9970 3.9954 3.9939 3.9924 3.9909 3.9894 3.9878 3.9863 85.0000 3.9996 3.9992 3.9989 3.9985 3.9981 3.9977 3.9973 3.9970 3.9966 90.0000 4.0000 4.0000 4.0000 4.0000 4.0000 4.0000 4.0000 4.0000 4.0000`

3.857822164681937           15            .35
indicating the best for this particular table is an area of 3.857822164681937  at alpha=15 degrees and x = 0.35.

The idea is then to concentrate on numbers around those values. The program was modified to be more generic with regard to the upper and lower bounds of x and alpha.

`        0.3000 0.3250 0.3500 0.3750 0.4000 0.4250 0.4500 0.4750 0.500010.0000 3.9023 3.8861 3.8687 3.850110.2778 3.9018 3.8856 3.8682 3.849610.5556 3.9014 3.8852 3.8677 3.849110.8333 3.9009 3.8847 3.8672 3.8485 3.828611.1111 3.9004 3.8842 3.8667 3.8480 3.828011.3889 3.9000 3.8837 3.8661 3.8474 3.827411.6667 3.8995 3.8831 3.8656 3.8468 3.826811.9444 3.8990 3.8826 3.8650 3.8462 3.826112.2222 3.8984 3.8820 3.8644 3.8456 3.825512.5000 3.8979 3.8815 3.8638 3.8449 3.824812.7778 3.8974 3.8809 3.8632 3.8443 3.827413.0556 3.8968 3.8803 3.8626 3.8436 3.8359 3.857413.3333 3.8963 3.8797 3.8619 3.8429 3.8444 3.865813.6111 3.8957 3.8791 3.8613 3.8423 3.8528 3.874213.8889 3.8951 3.8785 3.8606 3.8416 3.8611 3.882514.1667 3.8945 3.8778 3.8599 3.8447 3.8693 3.890714.4444 3.8939 3.8772 3.8592 3.8529 3.8774 3.898914.7222 3.8933 3.8765 3.8585 3.8609 3.8855 3.906915.0000 3.8926 3.8758 3.8578 3.8690 3.8935 3.9149 3.933315.2778 3.8920 3.8751 3.8571 3.8769 3.9014 3.9228 3.941215.5556 3.8913 3.8744 3.8570 3.8848 3.9093 3.9306 3.949015.8333 3.8907 3.8737 3.8648 3.8926 3.9170 3.9384 3.956716.1111 3.8900 3.8730 3.8725 3.9003 3.9247 3.9461 3.964416.3889 3.8893 3.8723 3.8802 3.9079 3.9323 3.9537 3.971916.6667 3.8886 3.8715 3.8878 3.9155 3.9399 3.9612 3.979416.9444 3.8879 3.8707 3.8954 3.9230 3.9473 3.9686 3.9868 4.002117.2222 3.8871 3.8719 3.9028 3.9304 3.9547 3.9759 3.9941 4.009417.5000 3.8864 3.8793 3.9102 3.9377 3.9620 3.9832 4.0014 4.016617.7778 3.8856 3.8867 3.9175 3.9450 3.9693 3.9904 4.0085 4.023718.0556 3.8849 3.8939 3.9248 3.9522 3.9764 3.9975 4.0156 4.030818.3333 3.8841 3.9012 3.9319 3.9593 3.9835 4.0045 4.0226 4.037718.6111 3.8833 3.9083 3.9390 3.9664 3.9905 4.0115 4.0295 4.044618.8889 3.8825 3.9154 3.9460 3.9733 3.9974 4.0183 4.0363 4.0513 4.063619.1667 3.8883 3.9224 3.9530 3.9802 4.0042 4.0251 4.0430 4.0580 4.070219.4444 3.8953 3.9294 3.9599 3.9870 4.0109 4.0318 4.0497 4.0646 4.076819.7222 3.9022 3.9362 3.9667 3.9937 4.0176 4.0384 4.0562 4.0711 4.083220.0000 3.9091 3.9430 3.9734 4.0004 4.0242 4.0449 4.0627 4.0776 4.0896`
`3.824829444556757           12.50000000000001           .4000000000000001`

bringing us down to area = 3.825.

This process was continued, leading to

area = 3.815441597154761   alpha = 12.03875805555555   x = .4125
(.0860364931384987,.4034277777352832) as the coordinates of the center of curvature of the arc of the segment in its new place.
width of rectangle = 1.5875    height of rectangle = 2.403427777735283  theta = 54.02019940252578

The chord length = 2 * sqrt(1 - (1-.4125)^2) ~= 1.618448330963951

The area relative to the original square is about .95386.

Edited on August 23, 2007, 10:57 am

Edited on August 23, 2007, 12:18 pm
 Posted by Charlie on 2007-08-23 10:55:42

 Search: Search body:
Forums (2)