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

 8 points no convex pentagon (Posted on 2009-10-09)
Find a set of 8 points with no three collinear such that no subset of 5 forms a convex pentagon.

 See The Solution Submitted by Jer No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution Comment 4 of 4 |

Start with four points arranged in a square, in its usual orientation (just for sake of argument). Arrange the remaining four points in a smaller square inside the first one, and tilted a small amount.

In the below program, the original square has its vertices 1 unit from the origin. The vertices of the smaller square are .75 units from the origin and the inner square is tilted 1/20 radian, or about 3 degrees, relative to the outer square.

The vertices are at:

`        x                             y .5561727685098583           .5031618542458078-.5031618542458079           .5561727685098582-.5561727685098583          -.5031618542458078 .5031618542458078          -.5561727685098583 .7071067811865476           .7071067811865475-.7071067811865475           .7071067811865476-.7071067811865477          -.7071067811865475 .7071067811865474          -.7071067811865477`

The program tests all combinations of 5 out of the 8 points, and finds none that are the vertices of a convex pentagon.

DECLARE FUNCTION norm# (x#)
DECLARE SUB pol2rect (rho#, theta#, x#, y#)
DECLARE SUB rect2pol (x#, y#, rho#, theta#)
DEFDBL A-Z
CLS
DIM SHARED pi, xPos(8), yPos(8)
pi = ATN(1) * 4
dr = pi / 180

i = 1
FOR r = .75# TO 1 STEP .25#
FOR angle = pi / 4 TO 2 * pi STEP pi / 2
IF r = 1 THEN th = angle:  ELSE th = angle - 1 / 20
pol2rect r, th, xPos(i), yPos(i)
PRINT xPos(i), yPos(i)
i = i + 1
NEXT angle
NEXT r
PRINT
FOR p1 = 1 TO 4
FOR p2 = p1 + 1 TO 5
FOR p3 = p2 + 1 TO 6
FOR p4 = p3 + 1 TO 7
FOR p5 = p4 + 1 TO 8
xc = (xPos(p1) + xPos(p2) + xPos(p3) + xPos(p4) + xPos(p5)) / 5
yc = (yPos(p1) + yPos(p2) + yPos(p3) + yPos(p4) + yPos(p5)) / 5
p(1) = p1: p(2) = p2: p(3) = p3: p(4) = p4: p(5) = p5
FOR i = 1 TO 5
rect2pol xPos(p(i)) - xc, yPos(p(i)) - yc, r, th(p(i))
NEXT
DO
done = 1
FOR i = 1 TO 4
IF th(p(i)) > th(p(i + 1)) THEN SWAP p(i), p(i + 1): done = 0
NEXT
LOOP UNTIL done

'  FOR i = 1 TO 5
'    PRINT xPos(p(i)); yPos(p(i)), th(p(i))
'  NEXT
'  PRINT
'  DO: LOOP UNTIL INKEY\$ > ""

x1 = xPos(p(5)): y1 = yPos(p(5))
prevAngle = 0
good = 1
FOR i = 1 TO 5
x2 = xPos(p(i)): y2 = yPos(p(i))
rect2pol x2 - x1, y2 - y1, dist, angle
IF norm(prevAngle - angle) > 0 THEN good = 0: EXIT FOR
prevAngle = angle
x1 = x2: y1 = y2
NEXT
IF good THEN
x2 = xPos(p(1)): y2 = yPos(p(1))
rect2pol x2 - x1, y2 - y1, dist, angle
IF norm(prevAngle - angle) > 0 THEN good = 0
IF good THEN
FOR i = 1 TO 5
PRINT xPos(p(i)); yPos(p(i)), th(p(i))
NEXT
PRINT
DO: LOOP UNTIL INKEY\$ > ""
END IF
END IF
NEXT
NEXT
NEXT
NEXT
NEXT

FUNCTION norm (x)
v = x
IF v > pi THEN v = v - 2 * pi
IF v < -pi THEN v = v + 2 * pi
norm = v
END FUNCTION

SUB pol2rect (rho, theta, x, y)
x = rho * COS(theta)
y = rho * SIN(theta)
END SUB

SUB rect2pol (x, y, rho, theta)
IF x > 0 THEN
theta = ATN(y / x)
rho = SQR(x * x + y * y)
ELSEIF x < 0 THEN
theta = ATN(y / x) + pi
rho = SQR(x * x + y * y)
ELSE
theta = pi / 2 * SGN(y)
rho = ABS(y)
END IF
IF theta < 0 THEN theta = theta + 2 * pi
END SUB

 Posted by Charlie on 2009-10-09 17:36:41

 Search: Search body:
Forums (0)