@inproceedings{4d9c8a1007504f968e8479336d07d032,

title = "Two-line center problem from a polar view: A new algorithm and data structure",

abstract = "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.",

author = "Jaromczyk, {Jerzy W.} and Miroslaw Kowaluk",

year = "1995",

doi = "10.1007/3-540-60220-8_47",

language = "English",

isbn = "3540602208",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "13--25",

editor = "Akl, {Selim G.} and Frank Dehne and J{\"o}rg-R{\"u}diger Sack and Nicola Santoro",

booktitle = "Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings",

note = "null ; Conference date: 16-08-1995 Through 18-08-1995",

}