The happy ending problem

Any 5 points in general position contain 4 in convex position. General position (no 3 collinear) is tested with exact integer cross products, and the convex quadrilateral is FOUND – its hull has 4 vertices – rather than merely asserted. With more than 5 points every 5-subset is checked, which is the theorem's statement, not a sample of it.

Usage

morie_happy_ending_quadrilateral(points)

Arguments

points

Two-column matrix of integer (x, y), distinct, no 3 collinear.

Value

A list with found, witness (matrix), every_five_subset.

References

Erdos P, Szekeres G (1935). A combinatorial problem in geometry. Compositio Mathematica, 2, 463-470.

Examples

morie_happy_ending_quadrilateral(rbind(c(0, 0), c(4, 0), c(2,
    1), c(1, 4), c(3, 5)))
#> $found
#> [1] TRUE
#> 
#> $witness
#>      [,1] [,2]
#> [1,]    0    0
#> [2,]    4    0
#> [3,]    3    5
#> [4,]    1    4
#> 
#> $every_five_subset
#> [1] TRUE
#> 
#> $estimate
#> [1] 1
#> 
#> $n
#> [1] 5
#> 
#> $method
#> [1] "Happy ending theorem (Erdos and Szekeres 1935)"
#>