×

Flight in a packing of disks. (English) Zbl 0767.52006

The author considers the problem of packing of disks in the plane consisting of pairwise disjoint convex domains, none of which contains the origin 0. Let \(\lambda(r)\) be the length of the shortest path which evades the domains and connects 0 with a point at a distance \(r\) from 0. The question is the following: What can be said for the supremum of the function \(\lambda(r)\) taken over all packings whose members are domains of diameter at least 2?
The author proves that there is a constant \(c\) such that, for \(r\geq 2\) \[ \lambda(r)\leq r^ 2+{1\over 2}\ln(r)+c \] and constructs a packing showing that, for \(r\geq\cot\bigl({\pi\over 9}\bigr)\) \[ \lambda(r)\geq r^ 2-\left({\pi\over 3}+{3\over\pi}\right)r+3.6. \] In the last section of the paper some interesting remarks connected with the examined problem can be found.

MSC:

52C15 Packing and covering in \(2\) dimensions (aspects of discrete geometry)
52A40 Inequalities and extremum problems involving convexity in convex geometry
52A37 Other problems of combinatorial convexity
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] I. Hortobágyi, Über die Durchlässigkeit einer aus Scheiben konstanter Breite bestehenden Schicht.Studia Sci. Math. Hungar.11 (1976), 383-387. · Zbl 0444.52013
[2] Fejes Tóth, G.; Gruber, P. M. (ed.); Wills, J. M. (ed.), New results in the theory of packing and covering (1983), Basel · Zbl 0533.52007
[3] A. Florian and H. Groemer, Two remarks on the permeability of layers of convex bodies.Studia Sci. Math. Hungar.20 (1985), 259-265. · Zbl 0085.44905
[4] J. S. B. Mitchell and C. H. Papadimitriou, Planning shortest paths.Proc. SIAM Conference on Geometric Modeling and Robotics, Albany, NY, 1985.
[5] E. Arkin, R. Connelly, and J. S. B. Mitchell, On monotone path among obstacles, with applications to planning assemblies.Proc. Fifth Annual ACM Symposium on Computational Geometry, Saarbrücken, June 1989, pp. 334-343.
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.