Efficient Algorithms for Unit-Disk-Graph Problems on Convex-Position Points
Polynomial-time exact algorithms for classically NP-hard optimization problems on the unit-disk graph of planar points — minimum dominating set, maximum independent set, discrete k-center, and dispersion — obtained by restricting the points to convex position. The convex ordering induces geometric monotonicity that dynamic programming and geometric data structures exploit to beat prior bounds (e.g. O(kn log n) dominating set, O(n^7/2) maximum independent set).
2501.00207
This computational-geometry paper studies several classical graph-optimization problems on the unit-disk graph G(P) of a planar point set P (two points adjacent iff their Euclidean distance is at mos…