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 ((Q2−P2)(R1−P1)−(Q1−P1)(R2−P2))((Q2−P2)(S1−P1)−(Q1−P1)(S2−P2))<0 and ((S2−R2)(P1−R1)−(S1−R1)(P2−R2))((S2−R2)(Q1−R1)−(S1−R1)(Q2−R2))<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