×

Optimizing generalized kernels of polygons. (English) Zbl 1473.51020

Summary: Let \(\mathcal{O}\) be a set of \(k\) orientations in the plane, and let \(P\) be a simple polygon in the plane. Given two points \(p, q\) inside \(P\), we say that \(p\mathcal{O}\)-sees \(q\) if there is an \(\mathcal{O}\)-staircase contained in \(P\) that connects \(p\) and \(q\). The \(\mathcal{O}\)-Kernel of the polygon \(P\), denoted by \(\mathcal{O}\)-Kernel\((P)\), is the subset of points of \(P\) which \(\mathcal{O}\)-see all the other points in \(P\). This work initiates the study of the computation and maintenance of \(\mathcal{O}\)-Kernel\((P)\) as we rotate the set \(\mathcal{O}\) by an angle \(\theta\), denoted by \(\mathcal{O}\)-Kernel\(_{\theta}(P)\). In particular, we consider the case when the set \(\mathcal{O}\) is formed by either one or two orthogonal orientations, \( \mathcal{O}=\{0^\circ\}\) or \(\mathcal{O}=\{0^\circ ,90^\circ\}\). For these cases and \(P\) being a simple polygon, we design efficient algorithms for computing the \(\mathcal{O}\)-Kernel\(_{\theta}(P)\) while \(\theta\) varies in \([-\frac{\pi}{2},\frac{\pi}{2})\), obtaining: (i) the intervals of angle \(\theta\) where \(\mathcal{O}\)-Kernel\(_{\theta}(P)\) is not empty, (ii) a value of angle \(\theta\) where \(\mathcal{O}\)-Kernel\(_{\theta }(P)\) optimizes area or perimeter. Further, we show how the algorithms can be improved when \(P\) is a simple orthogonal polygon. In addition, our results are extended to the case of a set \(\mathcal{O}=\{\alpha_1,\dots,\alpha_k\}\).

MSC:

51M20 Polyhedra and polytopes; regular figures, division of spaces
52A10 Convex sets in \(2\) dimensions (including convex curves)

References:

[1] Ackermann, W., Zum Hilbertschen Aufbau der reellen Zahlen, Math. Ann., 99, 118-133 (1928) · JFM 54.0056.06 · doi:10.1007/BF01459088
[2] de Berg, M.; Cheong, O.; van Kreveld, M.; Overmars, M., Computational Geometry: Algorithms and Applications (2008), Berlin: Springer, Berlin · Zbl 1140.68069 · doi:10.1007/978-3-540-77974-2
[3] Gewali, LP, Recognizing \(s\)-star polygons, Pattern Recogn., 28, 7, 1019-1032 (1995) · doi:10.1016/0031-3203(94)00158-I
[4] Hershberger, J., Finding the upper envelope of \(n\) line segments in \(O(n\log n)\) time, Inf. Process. Lett., 33, 4, 169-174 (1989) · Zbl 0689.68058 · doi:10.1016/0020-0190(89)90136-1
[5] Huskić, G.; Buck, S.; Zell, A., GeRoNa: generic robot navigation, J. Intell. Robot. Syst., 95, 2, 419-442 (2019) · doi:10.1007/s10846-018-0951-0
[6] Icking, C., Klein, R.: Searching for the kernel of a polygon: a competitive strategy. In: Proceedings of the 11th Annual Symposium on Computational Geometry, pp. 258-266 (1995)
[7] Ke, Y.; O’Rourke, J., Computing the kernel of a point set in a polygon, Lecture Notes in Computer Science, 382, 135-146 (1989) · Zbl 0767.68094 · doi:10.1007/3-540-51542-9_12
[8] Kirkpatrick, D. G., Snoeyink, J.: Computing common tangents without a separating line. Proceedings of the 4th International Workshop on Algorithms and Data Structures, pp. 183-193 (1995) · Zbl 1502.68328
[9] Lee, DT; Preparata, FP, An optimal algorithm for finding the kernel of a polygon, J. ACM, 26, 3, 415-421 (1979) · Zbl 0403.68051 · doi:10.1145/322139.322142
[10] McCallum, D.; Avis, D., A linear algorithm for finding the convex hull of a simple polygon, Inf. Process. Lett., 9, 5, 201-206 (1979) · Zbl 0423.68031 · doi:10.1016/0020-0190(79)90069-3
[11] Melkman, A., On-line construction of the convex hull of a simple polygon, Inf. Process. Lett., 25, 11-12 (1987) · Zbl 0653.68028 · doi:10.1016/0020-0190(87)90086-X
[12] Palios, L.: An output-sensitive algorithm for computing the \(s\)-kernel. 27th Canadian Conference on Computational Geometry, pp. 199-204 (2015)
[13] Palios, L., A new competitive strategy for reaching the kernel of an unknown polygon, Lecture Notes in Computer Science, 2000, 367-382 (1851) · Zbl 0966.68518
[14] Schuierer, S., Rawlins, G. J. E., Wood, D.: A generalization of staircase visibility. 3rd Canadian Conference on Computational Geometry, pp. 96-99 (1991)
[15] Schuierer, S., Wood, D.: Generalized kernels of polygons with holes. 5th Canadian Conference on Computational Geometry, pp. 222-227 (1993)
[16] Schuierer, S., Wood, D.: Multiple-guard kernels of simple polygons. Theoretical Computer Science Center Research Report HKUST-TCSC-98-06 (1998) · Zbl 1005.52001
[17] Sugihara, K., Smith, J.: Genetic algorithms for adaptive motion planning of an autonomous mobile robot. Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation, pp. 138-143 (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.