Endpoint Covering of Axis-Parallel Segments:Bichromatic and Monochromatic One-Center

Nandana Ghosh; Ankush Acharyya; Rakesh Gupta; Supantha Pandit

In the authors' words

We study exact one-center optimization for axis-parallel segments using axis-parallel squares under endpoint-based coverage, where a segment is $1$ -covered if the square contains at least one of its endpoints. In the monochromatic problem, we seek a minimum-side-length square that $1$ -covers all $n$ input segments. We obtain $O (n lo g n)$ -time algorithms for both unrestricted and segment-constrained centers. The unrestricted bound matches the known bound implied by the two-representative color-spanning-square problem, whereas the segment-constrained result is new. We also prove matching $Ω (n lo g n)$ lower bounds for both center models in the fixed-order algebraic decision-tree model. In the bichromatic problem, an admissible square must fully contain all $m$ blue segments, minimize the number of red segments with an endpoint in its interior, and, subject to this minimum, maximize its side length within a prescribed bounding box. We give deterministic $O (m + n lo g^{2} n)$ -time and $O (m + mn lo g n)$ -time algorithms for unrestricted and blue-segment-constrained centers, respectively.

Main resultThe abstract does not state a limitation.

Endpoint Covering of Axis-Parallel Segments:Bichromatic and Monochromatic One-Center

In the authors' words

More on Algorithms & complexity that day

A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond N4/3

A General Composition Theorem for Approximate Degree

Practical and Space-Efficient LZ77 and LZ Pre-Compression via String Synchronizing Sets

Sharp Lovasz-Theta Bounds on Random Graphs

A Human-Like Pedestrian Model for Automated Driving Simulations

A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$