We present a new algorithm for the two-line center problem (also called unweighted orthogonal L∞-fit problem): "Given a set S of n points in the real plane, find two closed strips whose union contains all of the points and such that the width of the wider strip is minimized." An almost quadratic 0(n2 log2 n) solution is given. The previously best known algorithm for this problem has time complexity 0(n2log6n) and uses a parametric search methodology. Our solution applies a new geometric structure, anchored lower and upper chains, and is based on examining several constraint versions of the problem. The anchored lower and upper chain structure is of interest by itself and provides a fast response to queries that involve planar configurations of points. The algorithm does not assume the general position of the input data points.
|Title of host publication||Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings|
|Editors||Selim G. Akl, Frank Dehne, Jörg-Rüdiger Sack, Nicola Santoro|
|Number of pages||13|
|State||Published - 1995|
|Event||4th Workshop on Algorithms and Data Structures, WADS 1995 - Kingston, Canada|
Duration: Aug 16 1995 → Aug 18 1995
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||4th Workshop on Algorithms and Data Structures, WADS 1995|
|Period||8/16/95 → 8/18/95|
Bibliographical notePublisher Copyright:
© 1995, Springer-Verlag. All rights reserved.
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science (all)