Halfspace separation in geodesic convexity
Niranjan Nair · 2026
Read Halfspace separation in geodesic convexity by Niranjan Nair (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-16159.txt.
Description
Nair studies halfspace separation in geodesic convexity on graphs. A set is convex if it holds every shortest path between its members. A halfspace is a convex set whose complement is also convex. The question is whether two given sets can be split by complementary halfspaces. Known to be hard in general graphs, the problem turns out to be solvable in polynomial time for matroid basis graphs, weakly bridged graphs, and pseudo-modular graphs.
Catalog record
| CREATOR | Niranjan Nair |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40166 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.16159