Capturing points with a rotating polygon (and a 3D extension). (English) Zbl 1431.68113
Rotation of an \(n\)-vertex simple polygon \(P\) around a fixed center to cover a maximum (or minimum) number out of \(m\) given points
of the plane is shown to be 3SUM-hard. A simple sweep over all critical angles where some given point crosses an edge of \(P\) solves this problem in \(O(nm\log(nm))\) time and \(O(nm)\) space. This complexity is often improved by way of a moving radius sweep-circle maintaining its intersection with \(P\).
This latter idea is then adapted to the extended problem where the rotation center may be moved along a segment, resulting in a plane-arrangement searchable for optimal depth, all of this in \(O(n^2m^2\log(nm))\) time and \(O(n^2m^2)\) space.
Finally, a method of this same complexity for the 3D version with fixed rotation center is outlined.
This latter idea is then adapted to the extended problem where the rotation center may be moved along a segment, resulting in a plane-arrangement searchable for optimal depth, all of this in \(O(n^2m^2\log(nm))\) time and \(O(n^2m^2)\) space.
Finally, a method of this same complexity for the 3D version with fixed rotation center is outlined.
Reviewer: Frank Plastria (Brussels)
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Agarwal, P.K., Flato, E., Halperin, D.: Polygon decomposition for efficient construction of Minkowski sums. Comput. Geom. Theory Appl. 21(1-2), 39-61 (2002) · Zbl 0991.68124 · doi:10.1016/S0925-7721(01)00041-4 |
| [2] | Agarwal, P.K., Hagerup, T., Ray, R., Sharir, M., Smid, M., Welzl, E.: Translating a planar object to maximize point containment. In: Algorithms — ESA 2002: 10th Annual European Symposium. Rome, Italy, September 17-21, 2002. Proceedings, pp. 42-53 (2002) · Zbl 1019.68134 |
| [3] | Baran, I., Demaine, E.D., Pǎtraṡcu, M.: Subquadratic algorithms for 3SUM. Algorithmica 50(4), 584-596 (2008) · Zbl 1147.68861 · doi:10.1007/s00453-007-9036-3 |
| [4] | Barequet, G., Dickerson, M., Pau, P.: Translating a convex polygon to contain a maximum number of points. Comput. Geom. Theory Appl. 8(4), 167-179 (1997) · Zbl 1133.52304 · doi:10.1016/S0925-7721(96)00011-9 |
| [5] | Barequet, G., Goryachev, A.: Offset polygon and annulus placement problems. Comput. Geom. Theory Appl. 47(3, Part A), 407-434 (2014) · Zbl 1283.52031 · doi:10.1016/j.comgeo.2013.10.003 |
| [6] | Barequet, G., Har-Peled, S.: Polygon containment and translation min-Hausdorff-distance between segment sets are 3SUM-hard. Int. J. Comput. Geom. Appl. 11(4), 465-474 (2001) · Zbl 1074.68629 · doi:10.1142/S0218195901000596 |
| [7] | Chazelle, B.: Advances in Computing Research, vol. 1, Chapter The polygon containment problem, pp. 1-33. JAI Press (1983) |
| [8] | Dickerson, M., Scharstein, D.: Optimal placement of convex polygons to maximize point containment. Comput. Geom. Theory Appl. 11(1), 1-16 (1998) · Zbl 0904.68175 · doi:10.1016/S0925-7721(98)00015-7 |
| [9] | Gajentaan, A., Overmars, M.H.: On a class of O(n2) problems in computational geometry. Comput. Geom. Theory nd Appl. 5(3), 165-185 (1995) · Zbl 0839.68105 · doi:10.1016/0925-7721(95)00022-2 |
| [10] | Grønlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. J. ACM (JACM) 65(4), 22 (2018) · Zbl 1422.68112 · doi:10.1145/3185378 |
| [11] | Ishiguro, H., Yamamoto, M., Tsuji, S.: Omni-directional stereo. IEEE Trans. Pattern Anal. Mach. Intell. 14(2), 257-262 (1992) · doi:10.1109/34.121792 |
| [12] | Kopelowitz, T., Pettie, S., Porat, E.: Higher lower bounds from the 3SUM conjecture. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1272-1287. Society for Industrial and Applied Mathematics (2016) · Zbl 1410.68147 |
| [13] | analysis, Tristan Needham.: Visual Complex Chapter 6.II.3: A Conformal Map of the Sphere, pp 283-286. Clarendon Press, Oxford (1998) |
| [14] | Pǎtraṡcu, M.: Towards polynomial lower bounds for dynamic problems. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 603-610. ACM (2010) · Zbl 1293.68153 |
| [15] | Yap, C.K., Chang, E.-C.: Algorithms for Robot Motion Planning and Manipulation, Chapter Issues in the Metrology of Geometric Tolerancing, pp 393-400. Wellesley, A.K. Peters (1997) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
