Find a set of 8 points with no three collinear such that no subset of 5 forms a convex pentagon.

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