Orthogonal partitions into four parts
By: Alexey Fakhrutdinov, Oleg R. Musin
Potential Business Impact:
Finds lines that cut shapes into four equal pieces.
The famous pancake theorem states that for every finite set $X$ in the plane, there exist two orthogonal lines that divide $X$ into four equal parts. We propose an algorithm whose running time is linear in the number of points in $X$ and prove that this complexity is optimal. We also consider generalizations of the pancake theorem and show that orthogonal hyperplanes can be found in polynomial time.
Similar Papers
Unavoidable patterns and plane paths in dense topological graphs
Combinatorics
Finds hidden patterns in connected dots.
Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm
Data Structures and Algorithms
Splits graph parts to help computers understand maps.
On Edge-Disjoint Maximal Outerplanar Graphs
Combinatorics
Builds many connected paths on a map.