Esther Klein Theorem

Overview

The Esther Klein simulation demonstrates the Happy Ending Problem: given n points in general position (no three collinear), what is the smallest n that guarantees a convex n-gon? This interactive element allows users to drag points on a grid and visualize convex hulls and collinearity errors.

Implementation Details

Grid System

The simulation uses a grid-based coordinate system where points snap to intersection points. The grid is rendered using SVG lines with themed colors, and points are HTML div elements positioned absolutely.

Points can be dragged with the mouse. During drag, the element checks if the target position is occupied by another point and prevents placement if so.

Collinearity Detection

The element checks all triplets of points for collinearity using the cross product formula:

$$(b_y - a_y) \cdot (c_x - b_x) == (c_y - b_y) \cdot (b_x - a_x)$$

When three or more points are collinear, the simulation draws error lines (red) connecting them instead of the convex hull.

Convex Hull Calculation

If no collinear triplets exist, the element calculates a convex hull using a configurable number of points (parameter figurePoints). The algorithm:

1. Generates all permutations of size figurePoints
2. Tests each for convexity by checking angle consistency
3. Selects the one with maximum area (or any valid for 10+ points)

The convexity test uses angle sum calculation, checking that the total rotation around the polygon is exactly $2\pi$ ($\pm 360^\circ$).

Automatic Distribution

On initialization, if no saved state exists, the element randomly distributes points across the grid, avoiding overlap. If collinear points are detected, it retries up to maxDistributionAttempts times (default 10) to find a valid configuration.

Resize Handling

When the viewport changes, the element recalculates the center position to keep the point configuration centered. It uses a closest-free-spot algorithm (breadth-first search) to reposition points if they would overlap after scaling.

Technical Considerations

The element stores point positions as both DOM styles (for rendering) and computational values (for algorithms). The getPermutations function generates all possible point selections with deduplication to avoid redundant checks.

State persistence saves point positions as grid coordinates rather than pixel values, making saved states resolution-independent.