Helly's theorem on the line

In one dimension the Helly number is 2: intervals meeting pairwise have a common point, \(\max_i a_i \le \min_i b_i\), and the witness interval is returned. Both facts are computed independently – every pair tested, then the global intersection formed – and the payload reports whether the implication held. When some pair is disjoint the theorem is silent and the pair is named (0-based, to match the Python mirror).

Usage

morie_helly_intervals(intervals)

Arguments

intervals

Two-column matrix of (a, b) with a <= b.

Value

A list with pairwise_intersecting, disjoint_pair, common_point_exists, witness, helly_holds.

References

Helly E (1923) Jahresbericht DMV 32:175-176.

Examples

D <- data.frame(x = c(1, 2, 3, 4), y = c(2, 4, 5, 9))
morie_helly_intervals(D)
#> $pairwise_intersecting
#> [1] FALSE
#> 
#> $disjoint_pair
#> [1] 0 2
#> 
#> $common_point_exists
#> [1] FALSE
#> 
#> $witness
#> NULL
#> 
#> $helly_holds
#> [1] TRUE
#> 
#> $estimate
#> [1] 0
#> 
#> $n
#> [1] 4
#> 
#> $method
#> [1] "Helly's theorem, d = 1 (Helly 1923)"
#>