The Two-Line Center Problem from a Polar View: A New Algorithm and Data Structure
作者： Jerzy W. Jaromczyk , Miroslaw Kowaluk
关键词: Binary search algorithm 、 Probabilistic analysis of algorithms 、 General position 、 Algorithm 、 Data point 、 Line (geometry) 、 Combinatorics 、 Time complexity 、 Data structure 、 Computer science 、 Convex hull
摘要: We present a new algorithm for the two-line center problem (also called unweighted orthogonal L∞-fit problem): “Given set S of n points in real plane, find two closed strips whose union contains all and such that width wider strip is minimized.” An almost quadratic O(n2 log2n) solution given. The previously best known this has time complexity O(n2log5n) uses parametric search methodology. Our applies geometric structure, anchored lower upper chains, based on examining several constraint versions problem. chain structure interest by itself provides fast response to queries involve planar configurations points. does not assume general position input data
springer.com
springerlink.com参考文章(12)
Nikolai M. Korneenko, Horst Martini, Hyperplane Approximation and Related Topics Springer Berlin Heidelberg. pp. 135- 161 ,(1993) , 10.1007/978-3-642-58043-7_7
Michael I. Shamos, Franco P. Preparata, Computational Geometry: An Introduction ,(1978)
Nimrod Megiddo, Arie Tamir, Finding Least-Distances Lines Siam Journal on Algebraic and Discrete Methods. ,vol. 4, pp. 207- 211 ,(1983) , 10.1137/0604021
Pankaj K. Agarwal, Micha Sharir, Planar geometric location problems and maintaining the width of a planar set symposium on discrete algorithms. pp. 449- 458 ,(1991) , 10.5555/127787.127865
Herbert Edelsbrunner, Algorithms in Combinatorial Geometry ,(1987)
R.L. Graham, An efficient algorith for determining the convex hull of a finite planar set Information Processing Letters. ,vol. 1, pp. 132- 133 ,(1972) , 10.1016/0020-0190(72)90045-2
Nimrod Megiddo, Arie Tamir, On the complexity of locating linear facilities in the plane Operations Research Letters. ,vol. 1, pp. 194- 197 ,(1982) , 10.1016/0167-6377(82)90039-6
Subhash Suri, John Herschberger, Offline maintenance of planar configurations symposium on discrete algorithms. pp. 32- 41 ,(1991) , 10.5555/127787.127801
D.T. Lee, Y.T. Ching, The power of geometric duality revisited Information Processing Letters. ,vol. 21, pp. 117- 122 ,(1985) , 10.1016/0020-0190(85)90015-8
Mark H. Overmars, Jan van Leeuwen, Maintenance of configurations in the plane Journal of Computer and System Sciences. ,vol. 23, pp. 166- 204 ,(1981) , 10.1016/0022-0000(81)90012-X