A faster algorithm for the two-center decision problem
作者： John Hershberger
DOI: 10.1016/0020-0190(93)90153-Z
关键词: Combinatorics 、 Decision problem 、 Plane (geometry) 、 Mathematics 、 Center (group theory) 、 Planar 、 Set (abstract data type) 、 Cluster analysis 、 Algorithm 、 Computational geometry 、 Binary logarithm
摘要: Abstract The planar two-center decision problem can be stated as follows: Given a set of n points in the plane and two radii r1 r2, determine whether covered by disks specified radii. This note presents an O(n2) algorithm for problem, which improves previous O(n2 log n) algorithm.
elsevier.com
sci-hub.se 参考文章(7)
B. M. Chazelle, D. T. Lee, On a circle placement problem Computing. ,vol. 36, pp. 1- 16 ,(1986) , 10.1007/BF02238188
John Hershberger, Subhash Suri, Finding tailored partitions Journal of Algorithms. ,vol. 12, pp. 431- 463 ,(1991) , 10.1016/0196-6774(91)90013-O
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
Harold N. Gabow, Robert Endre Tarjan, A linear-time algorithm for a special case of disjoint set union Journal of Computer and System Sciences. ,vol. 30, pp. 209- 221 ,(1985) , 10.1016/0022-0000(85)90014-5
Nimrod Megiddo, Kenneth J. Supowit, On the Complexity of Some Common Geometric Location Problems SIAM Journal on Computing. ,vol. 13, pp. 182- 196 ,(1984) , 10.1137/0213014
H. Edelsbrunner, D. Kirkpatrick, R. Seidel, On the shape of a set of points in the plane IEEE Transactions on Information Theory. ,vol. 29, pp. 551- 559 ,(1983) , 10.1109/TIT.1983.1056714
Vasilis Capoyleas, Günter Rote, Gerhard Woeginger, Geometric clusterings Journal of Algorithms archive. ,vol. 12, pp. 341- ,(1991) , 10.1016/0196-6774(91)90007-L