Abstract
For two convex bodies, C and D, consider a packing S of n positive homothets of C contained in D. We estimate the total perimeter of the bodies in S, denoted per(S), in terms of n. When all homothets of C touch the boundary of the container D, we show that either per(S) = O(logn) or per(S) = O(1), depending on how C and D “fit together,” and these bounds are the best possible apart from the constant factors. Specifically, we establish an optimal bound per(S) = O(logn) unless D is a convex polygon and every side of D is parallel to a corresponding segment on the boundary of C (for short, D is parallel to C). When D is parallel to C but the homothets of C may lie anywhere in D, we show that per(S) = O((1 + esc(S)) logn/loglogn), where esc(S) denotes the total distance of the bodies in S from the boundary of D. Apart from the constant factor, this bound is also the best possible.
Dumitrescu is supported in part by NSF (DMS-1001667). Tóth is supported in part by NSERC (RGPIN 35586) and NSF (CCF-0830734).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753–782 (1998)
Brass, P., Moser, W.O.J., Pach, J.: Research Problems in Discrete Geometry. Springer (2005)
Bern, M., Eppstein, D.: Approximation algorithms for geometric problems. In: Approximation Algorithms for NP-hard Problems, pp. 296–345. PWS (1997)
de Berg, M., Gudmundsson, J., Katz, M.J., Levcopoulos, C., Overmars, M.H., van der Stappen, A.F.: TSP with neighborhoods of varying size. J. Algorithms 57(1), 22–36 (2005)
Dumitrescu, A., Mitchell, J.S.B.: Approximation algorithms for TSP with neighborhoods in the plane. J. Algorithms 48(1), 135–159 (2003)
Dumitrescu, A., Tóth, C.D.: Minimum weight convex Steiner partitions. Algorithmica 60(3), 627–652 (2011)
Dumitrescu, A., Tóth, C.D.: The traveling salesman problem for lines, balls and planes, in. In: Proc. 24th SODA, pp. 828–843. SIAM (2013)
Levcopoulos, C., Lingas, A.: Bounds on the length of convex partitions of polygons. In: Joseph, M., Shyamasundar, R.K. (eds.) FSTTCS 1984. LNCS, vol. 181, pp. 279–295. Springer, Heidelberg (1984)
Mata, C., Mitchell, J.S.B.: Approximation algorithms for geometric tour and network design problems. In: Proc. 11th SOCG, pp. 360–369. ACM (1995)
Mitchell, J.S.B.: A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane. In: Proc. 26th SOCG, pp. 183–191. ACM (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dumitrescu, A., Tóth, C.D. (2013). On the Total Perimeter of Homothetic Convex Bodies in a Convex Container. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2013 2013. Lecture Notes in Computer Science, vol 8096. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40328-6_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-40328-6_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40327-9
Online ISBN: 978-3-642-40328-6
eBook Packages: Computer ScienceComputer Science (R0)