PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Nandana Ghosh, Ankush Acharyya, Rakesh Gupta, Supantha Pandit

arXiv:2609.29821v1cs.CG

TL;DR

The paper asks how to optimize axis-parallel squares for endpoint-covered monochromatic segments and for bichromatic segments with mandatory blue containment and red-endpoint conflicts. It develops coordinate-decomposition and depth-based algorithms for unrestricted and segment-constrained centers, obtaining O(n log n) monochromatic algorithms, matching lower bounds, and deterministic bichromatic algorithms with bounds that depend on the center domain.

  • Problem

    The paper studies minimum squares that 1-cover every monochromatic segment and, for bichromatic inputs, squares that contain all blue segments while lexicographically minimizing red endpoint conflicts and maximizing side length.

    Source: §1 · pp. 1–2

  • Method

    It uses a coordinate decomposition for monochromatic coverage and rectangle-depth and lower-envelope structures for the bichromatic objectives.

    Source: §1 · p. 3, §4 · p. 38

  • Results

    O(n log n) time solves both monochromatic variants with matching Ω(n log n) lower bounds; bichromatic algorithms take deterministic O(m + n log^2 n) and O(m + mn log n) time for unrestricted and blue-segment-constrained centers, respectively.

    Source: §1 · p. 3, §2.4 · p. 11, Secondary optimization on a blue segment · p. 35

  • Takeaways & Limitations

    The unrestricted monochromatic bound is known from the two-representative color-spanning-square problem, while the segment-constrained algorithm and matching lower bounds are contributions of this work.

    Source: §1 · p. 3

    The paper leaves open reducing the logarithmic factor in the continuous bichromatic bound and extending the techniques to rectangles, higher-dimensional boxes, and other variants.

    Source: §4 · p. 38

Abstract

from arXiv · show

We study exact one-center optimization for axis-parallel segments using axis-parallel squares under endpoint-based coverage, where a segment is \emph{$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\log 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 $\Omega(n\log 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\log^2 n)$-time and $O(m+mn\log n)$-time algorithms for unrestricted and blue-segment-constrained centers, respectively.

1 Introduction

The paper studies two axis-parallel-square one-center problems for axis-parallel segments, using endpoint-based coverage: monochromatic squares select an endpoint from each segment, while bichromatic squares contain blue segments and penalize red-endpoint conflicts. It gives algorithms for unrestricted and segment-constrained centers, with matching lower bounds for both monochromatic variants.

1 Introduction

  • Monochromatic squares minimize side length while 1-covering every segment; bichromatic squares fully contain blue segments, minimize red endpoint conflicts, then maximize side length within U.The center is unrestricted or constrained to an input segment, and to a blue segment in the bichromatic discrete variant.Source: §1 · pp. 1–2
  • The bichromatic objective is a segment-valued analogue of MinRed classification, with mandatory blue objects and red segments charged when either endpoint lies strictly inside the square.Unlike point-based facility-location models, the objects are segments and each red segment contributes one conflict; the secondary objective maximizes side length within U.Source: §1 · pp. 2–3
  • O(n log n)-time algorithms solve both monochromatic center variants, and matching Ω(n log n) lower bounds hold even for collinear equal-length vertical segments.The unrestricted bound matches the known two-representative color-spanning-square bound; the segment-constrained result is new.Source: §1 · p. 3
  • O(m + n log^2 n) time suffices for unrestricted bichromatic centers, while blue-segment-constrained centers take O(m + mn log n) time.The continuous method uses rectangle depth and critical side lengths; the discrete method separates the objectives using interval depth and a restricted lower envelope.Source: §1 · p. 3
  • The algorithms allow equal coordinates, coincident endpoints, and coincident segments, and explicitly handle simultaneous sweep events and strict-interior constraints.The paper retains multiplicity and makes no general-position assumption.Source: §1 · p. 3

2 Monochromatic One-Center Problem

This section studies the discrete monochromatic one-center problem, expressing the minimum 1-cover square size at a fixed center through independent coordinate functions and using them to address unrestricted and segment-constrained centers. It gives an O(n log n)-time, O(n)-space algorithm and proves Ω(n log n) lower bounds for both center variants via a Max Gap reduction.

2.1 Coordinate Decomposition

  • For every center (x, y), the minimum half-side length is H(x, y) = max{A(x), B(y)}, separating the horizontal and vertical coordinate requirements.This identity is the structural basis for both center variants.Source: §2.1 · p. 4
  • The continuous piecewise-linear functions A and B each have O(n) pieces and can be constructed in O(n log n) time and O(n) space.The construction uses four partial envelopes for each orientation, each with O(n) total pieces and constructible in O(n log n) time.Source: §2.1 · pp. 5–6

2.2 Continuous One-Center Problem

  • The unrestricted optimum is found by independently minimizing A(x) and B(y), giving an O(n log n)-time, O(n)-space algorithm.After constructing the representations, a linear scan finds minimizing coordinates for both functions.Source: §2.2 · p. 8

2.3 Discrete One-Center Problem

  • For the discrete variant, O(n) preprocessing supports point evaluation and interval minima with attaining points for A and B in O(log n) per query.The piecewise-linear representations are augmented with binary-search lookup and range-minimum structures.Source: §2.3 · p. 9
  • On each input segment, minimizing H reduces to an interval-minimum query on the varying coordinate function and an evaluation at the fixed coordinate.The fixed coordinate contributes a constant along the segment, while the other coordinate ranges over the segment's interval.Source: §2.3 · pp. 9–10
  • The discrete 1-cover one-center optimum can be computed in O(n log n) time and O(n) space, with an optimal square centered on an input segment.The algorithm builds piecewise-linear functions A and B, then processes each segment using a point evaluation and an interval-minimum query.Source: §2.3 · pp. 10–11

2.4 Lower Bound on the Monochromatic One-Center Problem

  • An O(n)-time reduction from Max Gap gives Ω(n log n) lower bounds for continuous and discrete variants, even for equal-length collinear vertical segments, with optimum R − ∆ encoding the gap.The constructed instance has the same optimum for both variants.Source: §2.4 · pp. 11, 13

3 Bichromatic One-Center Problem

This section develops bichromatic one-center methods for squares that minimize the number of red segments with an endpoint inside, then maximize side length within the prescribed box. It covers unrestricted and blue-segment-constrained centers through continuous and discrete analyses.

3 Bichromatic One-Center Problem

  • An admissible square fully contains every blue segment, minimizes red segments with an endpoint in its interior, then maximizes side length within the prescribed box.A red segment counts once if either endpoint is strictly inside; endpoints on the boundary do not contribute.Source: §3 · p. 13

3.1 Continuous One-Center Problem

  • For every feasible side length, admissible lower-left corners form a nonempty axis-parallel rectangle computable in O(1); feasibility holds exactly when L0 ≤ LU.L0 is the minimum side length covering the blue endpoint bounding rectangle, and LU is the largest square side length allowed by the box.Source: Feasible lower-left corners and nesting · p. 14, §3.1 · p. 14
  • The continuous primary optimum is attained at the smallest feasible side length L0; every lexicographically optimal square contains a side-L0 square with the same minimum penalty.The minimum red penalty is κ(L0), and the nested side-L0 square has that penalty.Source: Monotonicity of the primary objective · pp. 15–16
  • For a prescribed side length, a vertical sweep computes the minimum red penalty and an attaining square in O(n log n) time and O(n) space.The sweep finds a minimum-depth point among open forbidden rectangles, whose depth equals the red penalty.Source: Fixed-side-length optimization · pp. 17, 19
  • Between consecutive critical values, the minimum red penalty κ(L) is constant, so the maximum penalty-preserving side length can be found among critical values.The critical values themselves must be retained because boundary contact does not count as a red endpoint in the square interior.Source: Critical side lengths · pp. 20–21
  • The largest side length preserving the minimum red penalty is attained and belongs to the critical set C.The critical set consists of absolute differences between input endpoint coordinates and the bounding-box coordinates; the optimum cannot lie inside an interval where the penalty is constant.Source: Critical side lengths · pp. 20–21, Fixed-side-length optimization · p. 20

Implicit critical-value search

  • The nonnegative entries of two implicitly represented row- and column-sorted difference matrices are exactly the critical coordinate differences, enabling deterministic O(n) rank selection without materializing them.The matrices retain multiplicities for global rank selection.Source: Implicit critical-value search · pp. 22–23
  • The search uses the nonincreasing penalty-preservation predicate to discard at least half the surviving rank interval per iteration, requiring O(log n) iterations.Each iteration selects a pivot and evaluates its red penalty.Source: Implicit critical-value search · p. 24
  • After sorting X and Y, the implicit critical-value search takes O(n log^2 n) time and O(n) additional working space.It repeatedly selects a median surviving matrix value and evaluates whether that value preserves the minimum red penalty.Source: Implicit critical-value search · p. 24
  • O(m + n log^2 n) time and O(n) additional space suffice for the continuous problem, producing a square that minimizes red penalty and then maximizes side length.The algorithm uses implicit critical-value search rather than explicitly constructing the potentially quadratic critical-value set.Source: Implicit critical-value search · p. 26

3.2 Discrete One-Center Problem

  • For each blue segment, feasible center positions form an empty set or a closed interval computable in O(1) time.Feasibility requires the half-side needed to cover the blue bounding rectangle to be no greater than the maximum permitted by the bounding box.Source: Feasible centers and red-distance curves · p. 27
  • Each red segment is counted precisely when its endpoint-distance threshold is strictly below the square’s half-side; for a fixed blue segment, this threshold is continuous and piecewise linear.Each threshold has O(1) affine pieces with slopes in {−1, 0, +1}.Source: Feasible centers and red-distance curves · p. 27
  • O(n) time per blue segment computes its minimum red penalty and primary-optimal locus using ordered event lists and a linear sweep.At the minimum-blue-radius locus, red-segment contributions are represented by weighted intervals; the outer feasible branches are nested and their red penalty is nondecreasing away from that locus.Source: Primary optimization on a blue segment · pp. 29–31
  • For each blue-segment candidate, the minimum red penalty ki and its primary-optimal center locus Zi are computed in O(n) time, with Zi having O(n) combinatorial complexity.The locus representation records maximal intervals and isolated points, including endpoint inclusion.Source: Primary optimization on a blue segment · p. 32
  • The discrete sweeps handle coincident events, coincident red segments, and loci or components degenerating to points exactly, without symbolic perturbation or general-position assumptions.Events at the same parameter coordinate are processed together, and degenerate points are evaluated and stored explicitly.Source: Primary optimization on a blue segment · p. 32
  • The secondary optimum is attained, with largest admissible half-side min{νi(x), λi(x)} on Zi; boundary contact by a red endpoint preserves the penalty because only interior endpoints count.Here λi(x) is the first half-side at which an uncounted red segment reaches the square boundary, and νi(x) enforces containment in the bounding box.Source: Secondary optimization on a blue segment · pp. 33, 37
  • For each candidate blue segment, λi has O(n) complexity and is constructed in O(n log n) time using O(n) space; given Zi, the optimal half-side and an attaining center take O(n) additional time.The construction forms a lower envelope of restricted red-distance curves, grouped into three slope classes.Source: Secondary optimization on a blue segment · pp. 33–34
  • The discrete problem is solved deterministically in O(m+mn log n) time using O(n) additional working space.The returned square is lexicographically optimal: it minimizes the red penalty, then maximizes side length among squares attaining that minimum.Source: Secondary optimization on a blue segment · pp. 35, 37
  • Sorting red endpoints by x- and y-coordinate takes O(n log n) time and O(n) space and is performed only once.Source: Secondary optimization on a blue segment · p. 37
  • O(n log n) time per blue candidate finds an attaining center, using globally sorted red endpoint orders.For a fixed blue segment, β_i, ν_i, and I_i are obtained in O(1) time, while k_i and Z_i take O(n) time to compute.Source: Secondary optimization on a blue segment · p. 37
  • O(m + mn log n) time and O(n) additional space suffice to process all m blue segments.The one-time O(n log n) sorting cost is absorbed when n and m are at least 1; the O(m) computation of T_B is included in the total.Source: Secondary optimization on a blue segment · p. 37

4 Concluding Remarks

Coordinate decomposition yields optimal O(n log n)-time monochromatic algorithms for both center domains; for bichromatic problems, bounding-rectangle, depth, and lower-envelope techniques give deterministic algorithms for both domains. Open directions include reducing the continuous bichromatic bound’s logarithmic factor and extending the methods to other settings.

4 Concluding Remarks

  • O(n log n)-time optimal algorithms solve the monochromatic problem for both unrestricted and segment-constrained centers.The coordinate decomposition separates horizontal and vertical requirements.Source: §4 · p. 38
  • Deterministic bichromatic algorithms take O(m+n log^2 n) time for unrestricted centers and O(m+mn log n) for blue-segment-constrained centers.The approach uses blue bounding rectangles and red-conflict depth and lower-envelope structures.Source: §4 · p. 38
  • Open questions include reducing the continuous bichromatic bound’s logarithmic factor without explicitly generating the quadratic critical set.Other directions include more global coupling of candidate blue segments and extensions to rectangles, higher-dimensional boxes, weighted conflicts, or more representatives.Source: §4 · p. 38
Loading 2609.29821v1…