Processing math: 100%

Sunday, June 28, 2020

Polly Gawn's Dot Connector

What is the greatest possible number of unique hexagons Polly can draw using six points?

For any 6 vertices v1,,v6 and any permutation σS6, we can draw an edge from vσi to vσi+1 for i=1,,6. Polly would need to check that the edges do not intersect one another (besides at shared vertices) in order to verify that σ defines a hexagon.

Line segments 1=PQ and 2=RS intersect if and only if ((Q2P2)(R1P1)(Q1P1)(R2P2))((Q2P2)(S1P1)(Q1P1)(S2P2))<0 and ((S2R2)(P1R1)(S1R1)(P2R2))((S2R2)(Q1R1)(S1R1)(Q2R2))<0.
Luckily Polly has chosen a reasonably small number of dots to connect, so that she can brute force the solution. There are |S6|=6!=720 possible permutations, though each possible hexagon is described by 12 such permutations: 6 labels for vertex with largest y-value and two orientations (clockwise and counterclockwise).

Polly spun up the old Monte Carlo simulator and generated N=10,000 random sets of 6 vertices, checked whether each of the 720 possible permutations defined a hexagon, then divided by 12. The maximum number of unique hexagons was 29. This particular configuration involves two nested, but not concentric triangles, e.g., v1=(3.933833017,2.610569057),v2=(9.739640057,8.188125177),v3=(2.408262249,7.450428529), v4=(0.795494503,9.711307153),v5=(4.004793527,4.769703033),v6=(5.950340459,7.124276426).

No comments:

Post a Comment