Published in

Elsevier, Discrete Applied Mathematics, (239), p. 106-118, 2018

DOI: 10.1016/j.dam.2017.12.028

Links

Tools

Export citation

Search in Google Scholar

Dispersing Points on Intervals

Journal article published in 2016 by Shimin Li ORCID, Haitao Wang
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

We consider a problem of dispersing points on disjoint intervals on a line. Given n pairwise disjoint intervals sorted on a line, we want to find a point in each interval such that the minimum pairwise distance of these points is maximized. Based on a greedy strategy, we present a linear time algorithm for the problem. Further, we also solve in linear time the cycle version of the problem where the intervals are given on a cycle. ; Comment: A preliminary version to appear in ISAAC 2016