Separating overlapped intervals on a line

DOI10.20382/JOCG.V10I1A11zbMATH Open1494.68273arXiv1609.07766OpenAlexW3046560834MaRDI QIDQ5207869FDOQ5207869

Authors: Shimin Li, Haitao Wang 

Publication date: 13 January 2020

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.

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

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

Mathematics Subject Classification ID

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

Cited In (1)

• Title not available (Why is that?)

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)