Separating overlapped intervals on a line

DOI10.20382/JOCG.V10I1A11MaRDI QIDQ5207869zbMATH OpenOpenAlexFDO

Authors Shimin Li, Haitao Wang

Publication date 13 January 2020

Full work available at URL https://arxiv.org/abs/1609.07766

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Given $n$ intervals on a line $ell$, we consider the problem of moving these intervals on $ell$ such that no two intervals overlap and the maximum moving distance of the intervals is minimized. The difficulty for solving the problem lies in determining the order of the intervals in an optimal solution. By interesting observations, we show that it is sufficient to consider at most $n$ "candidate" lists of ordered intervals. Further, although explicitly maintaining these lists takes $Omega(n^2)$ time and space, by more observations and a pruning technique, we present an algorithm that can compute an optimal solution in $O(nlogn)$ time and $O(n)$ space. We also prove an $Omega(nlogn)$ time lower bound for solving the problem, which implies the optimality of our algorithm.

Recommendations

• On separating points by lines
• scientific article; zbMATH DE number 6850368
• On separating convex points with lines
• SEPARATING POINTS BY AXIS-PARALLEL LINES
• Separating convex sets by straight lines
• Separating and shattering long line segments
• Separating and shattering long line segments
• A random-line-graph approach to overlapping line segments
• scientific article; zbMATH DE number 2079753
• Separation of two sets by piecewise linear function

Cited in

(1)

• scientific article; zbMATH DE number 6850368 (Why is no real title available?)

This page was built for publication: Separating overlapped intervals on a line

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207869)