For any 6 vertices $v_1, \dots, v_6$ and any permutation $\sigma \in S_6,$ we can draw an edge from $v_{\sigma_i}$ to $v_{\sigma_{i+1}}$ for $i = 1, \dots, 6.$ Polly would need to check that the edges do not intersect one another (besides at shared vertices) in order to verify that $\sigma$ defines a hexagon.
Line segments $\ell_1 = PQ$ and $\ell_2 = RS$ intersect if and only if $$((Q_2-P_2)(R_1-P_1)-(Q_1-P_1)(R_2-P_2)) ((Q_2-P_2)(S_1-P_1)-(Q_1-P_1)(S_2-P_2)) < 0$$ and $$((S_2-R_2)(P_1-R_1)-(S_1-R_1)(P_2-R_2)) ((S_2-R_2)(Q_1-R_1)-(S_1-R_1)(Q_2-R_2)) < 0.$$
Luckily Polly has chosen a reasonably small number of dots to connect, so that she can brute force the solution. There are $|S_6| = 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., $$v_1 = (3.933833017, 2.610569057), v_2 = (9.739640057, 8.188125177), v_3 = (2.408262249, 7.450428529),$$ $$v_4 = (0.795494503, 9.711307153), v_5 = (4.004793527, 4.769703033), v_6 = (5.950340459, 7.124276426).$$
No comments:
Post a Comment