Abstract
Let P and Q be two simple polygons in the plane of total complexity n, each of which can be decomposed into at most k convex parts. We present an (1 − ε)-approximation algorithm, for finding the translation of Q, which maximizes its area of overlap with P. Our algorithm runs in Ocn time, where c is a constant that depends only on k and ε.
This suggest that for polygons that are “close” to being convex, the problem can be solved (approximately), in near linear time.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ahn, H.K., Cheng, S.W., Kweon, H.J., Yon, J.: Overlap of convex polytopes under rigid motion. Comput. Geom. Theory Appl. 47(1), 15–24 (2014), http://dx.doi.org/10.1016/j.comgeo.2013.08.001
Ahn, H.K., Cheng, S.W., Reinbacher, I.: Maximum overlap of convex polytopes under translation. Comput. Geom. Theory Appl. 46(5), 552–565 (2013), http://dx.doi.org/10.1016/j.comgeo.2011.11.003
Ahn, H.K., Cheong, O., Park, C.D., Shin, C.S., Vigneron, A.: Maximizing the overlap of two planar convex sets under rigid motions. Comput. Geom. Theory Appl. 37(1), 3–15 (2007)
Alt, H., Fuchs, U., Rote, G., Weber, G.: Matching convex shapes with respect to the symmetric difference. Algorithmica 21, 89–103 (1998), http://citeseer.nj.nec.com/267158.html
Alt, H., Guibas, L.J.: Discrete geometric shapes: Matching, interpolation, and approximation. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 121–153. Elsevier (2000)
Avis, D., Bose, P., Toussaint, G.T., Shermer, T.C., Zhu, B., Snoeyink, J.: On the sectional area of convex polytopes. In: Proc. 12th Annu. Sympos. Comput. Geom., pp. 411–412 (1996)
Barequet, G., Har-Peled, S.: Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. J. Algorithms 38, 91–109 (2001), http://cs.uiuc.edu/~sariel/research/papers/98/bbox.html
Barequet, G., Har-Peled, S.: Polygon containment and translational min-hausdorff-distance between segment sets are 3sum-hard. Internat. J. Comput. Geom. Appl. 11(4), 465–474 (2001)
de Berg, M., Cabello, S., Giannopoulos, P., Knauer, C., van Oostrum, R., Veltkamp, R.C.: Maximizing the area of overlap of two unions of disks under rigid motion. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 138–149. Springer, Heidelberg (2004)
de Berg, M., Cheong, O., Devillers, O., van Kreveld, M., Teillaud, M.: Computing the maximum overlap of two convex polygons under translations. Theo. Comp. Sci. 31, 613–628 (1998), http://link.springer-ny.com/link/service/journals/00224/bibs/31n5p613.html
Chazelle, B., Liu, D., Magen, A.: Sublinear geometric algorithms. SIAM J. Comput. 35(3), 627–646 (2005)
Vigneron, A.: Geometric optimization and sums of algebraic functions. ACM Trans. Algo. 4, 1–4 (2014), http://doi.acm.org/10.1145/2532647
Cheong, O., Efrat, A., Har-Peled, S.: On finding a guard that sees most and a shop that sells most. Discrete Comput. 37(4), 545–563 (2007), http://link.springer-ny.com/link/service/journals/00454/
Gritzmann, P., Klee, V.: Inner and outer j-radii of convex bodies in finite-dimensional normed spaces. Discrete Comput. Geom. 7, 255–280 (1992), http://link.springer-ny.com/link/service/journals/00454/
Har-Peled, S.: Geometric Approximation Algorithms. Mathematical Surveys and Monographs, vol. 173. Amer. Math. Soc. (2011)
Har-Peled, S., Roy, S.: Approximating the maximum overlap of polygons under translation. CoRR abs/1406.5778 (2014), http://arxiv.org/abs/1406.5778
Keil, J.M., Snoeyink, J.: On the time bound for convex decomposition of simple polygons. Internat. J. Comput. Geom. Appl. 12(3), 181–192 (2002)
Mount, D.M., Silverman, R., Wu, A.Y.: On the area of overlap of translated polygons. Computer Vision and Image Understanding: CVIU 64(1), 53–61 (1996), http://www.cs.umd.edu/~mount/Papers/overlap.ps
Sharir, M., Toledo, S.: Extremal polygon containment problems. Comput. Geom. Theory Appl. 4, 99–118 (1994)
Toussaint, G.T.: Solving geometric problems with the rotating calipers. In: Proc. IEEE MELECON 1983. pp. A10.02/1–4 (1983)
Vigneron, A.: Geometric optimization and sums of algebraic functions. ACM Trans. Algo. 4, 1–4 (2014), http://doi.acm.org/10.1145/2532647
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Har-Peled, S., Roy, S. (2014). Approximating the Maximum Overlap of Polygons under Translation. In: Schulz, A.S., Wagner, D. (eds) Algorithms - ESA 2014. ESA 2014. Lecture Notes in Computer Science, vol 8737. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44777-2_45
Download citation
DOI: https://doi.org/10.1007/978-3-662-44777-2_45
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44776-5
Online ISBN: 978-3-662-44777-2
eBook Packages: Computer ScienceComputer Science (R0)