Constrained Square-Center Problems
作者： Matthew J. Katz , Klara Kedem , Michael Segal
DOI: 10.1007/BFB0054358
关键词:
摘要: Given a set P of n points in the plane, we seek two squares whose center belong to P, their union contains and area larger square is minimal. We present efficient algorithms for three variants this problem: In first axe axis parallel, second they are free rotate but must remain parallel each other, third independently.
springer.com
sci-hub.st 参考文章(20)
Jerzy W. Jaromczyk, Miroslaw Kowaluk, The Two-Line Center Problem from a Polar View: A New Algorithm and Data Structure workshop on algorithms and data structures. pp. 13- 25 ,(1995) , 10.1007/3-540-60220-8_47
Michael Segal, On Piercing Sets of Axis-Parallel Rectangles and Rings european symposium on algorithms. pp. 430- 442 ,(1997) , 10.1007/3-540-63397-9_33
Alex Glozman, Klara Kedem, Gregory Shpitalnik, On Some Geometric Selection and Optimization Problems via Sorted Matrices workshop on algorithms and data structures. pp. 26- 37 ,(1995) , 10.1007/3-540-60220-8_48
Richard Cole, Parallel merge sort SIAM Journal on Computing. ,vol. 17, pp. 770- 785 ,(1988) , 10.1137/0217049
Matthew J. Katz, Micha Sharir, An Expander-Based Approach to Geometric Optimization SIAM Journal on Computing. ,vol. 26, pp. 1384- 1408 ,(1997) , 10.1137/S0097539794268649
M. Sharir, A Near-Linear Algorithm for the Planar 2-Center Problem Discrete and Computational Geometry. ,vol. 18, pp. 125- 134 ,(1997) , 10.1007/PL00009311
Greg N. Frederickson, Donald B. Johnson, Generalized Selection and Ranking: Sorted Matrices SIAM Journal on Computing. ,vol. 13, pp. 14- 30 ,(1984) , 10.1137/0213002
David Eppstein, Faster construction of planar two-centers symposium on discrete algorithms. pp. 131- 138 ,(1997) , 10.5555/314161.314198
Matthew J. Katz, Franck Nielsen, On piercing sets of objects symposium on computational geometry. pp. 113- 121 ,(1996) , 10.1145/237218.237253
Pankaj K. Agarwal, Micha Sharir, Planar geometric location problems Algorithmica. ,vol. 11, pp. 185- 195 ,(1994) , 10.1007/BF01182774