Algorithms for orthogonal partitioning into four parts
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914297520586752 |
|---|---|
| author | Fakhrutdinov, Alexey Musin, Oleg R. |
| author_facet | Fakhrutdinov, Alexey Musin, Oleg R. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_20866 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algorithms for orthogonal partitioning into four parts Fakhrutdinov, Alexey Musin, Oleg R. Combinatorics Computational Geometry Metric Geometry 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. |
| title | Algorithms for orthogonal partitioning into four parts |
| topic | Combinatorics Computational Geometry Metric Geometry |
| url | https://arxiv.org/abs/2511.20866 |