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

CREATORNiranjan Nair
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40166
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.16159

Browse the full library · About the Tower of Babel