Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-29T07:51:51.584Z Has data issue: false hasContentIssue false
  • English
  • Français

Quantitative Illumination of Convex Bodies and Vertex Degrees of Geometric Steiner Minimal Trees

Part of: General convexity Graph theory

Published online by Cambridge University Press:  21 December 2009

Konrad J. Swanepoel
Konrad J. Swanepoel
Affiliation:
Department of Mathematical Sciences, University of South Africa, PO Box 392, Pretoria 0003, South Africa. E-mail: [email protected]
Get access

Abstract

Two results are proved involving the quantitative illumination parameter B(d) of the unit ball of a d-dimensional normed space introduced by Bezdek (1992). The first is that B(d) = O(2dd2 log d). The second involves Steiner minimal trees. Let v(d) be the maximum degree of a vertex, and s(d) that of a Steiner point, in a Steiner minimal tree in a d-dimensional normed space, where both maxima are over all norms. Morgan (1992) conjectured that s(d) ≤ 2d, and Cieslik (1990) conjectured that v(d) ≤ 2(2d − 1). It is proved that s(d) ≤ v(d) ≤ B(d) which, combined with the above estimate of B(d), improves the previously best known upper bound v(d) < 3d.

MSC classification

Secondary: 52A37: Other problems of combinatorial convexity 05C05: Trees
Type
Research Article
Information
Mathematika , Volume 52 , Issue 1-2 , December 2005 , pp. 47 - 52
Copyright
Copyright © University College London 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[Bez92]Bezdek, K., Research problem 46. Period. Math. Hungar. 24 (1992), 119–121.CrossRefGoogle Scholar
[Bra01]Brazil, M., Steiner minimum trees in uniform orientation metrics. In Steiner trees in industry, Comb. Optim., vol. 11, Kluwer Acad. Publ. (Dordrecht, 2001), 1–27.CrossRefGoogle Scholar
[BTW00]Brazil, M., Thomas, D. A., and Weng, J. F., Minimum networks in uniform orientation metrics. SIAM J. Comput 39 (2000), 1579–1593.CrossRefGoogle Scholar
[Cie90]Cieslik, D., Knotengrade kürzester Bäume in endlich-dimensionalen Banachräumen. Rostock. Math. Kolloq. 39 (1990), 89–93.Google Scholar
[Cie98]Cieslik, D., Steiner minimal trees. Nonconvex Optimization and its Applications 23, Kluwer Acad. Publ. (Dordrecht, 1998).Google Scholar
[Coc67]Cockayne, E. J., On the Steiner problem. Canad. Math. Bull. 10 (1967), 431–450.CrossRefGoogle Scholar
[Gro61]Groemer, H., Abschätzungen für die Anzahl der konvexen Körper, die einen konvexen Körper berühren. Monatsh. Math. 65 (1961), 74–81.CrossRefGoogle Scholar
[Grü63a]Grünbaum, B., On a conjecture of H. Hadwiger. Pacific J. Math. 11 (1961), 215–219.CrossRefGoogle Scholar
[Grü63b]Grünbaum, B., Borsuk's problem and related questions. Proc. Sympos. Pure Math. Vol. VII, Amer. Math. Soc. (Providence, R.I., 1963), 271–284.Google Scholar
[Had57]Hadwiger, H., Über Treffanzahlen bei translationsgleichen Eikörpern, Arch. Math. 8 (1957), 212–213.CrossRefGoogle Scholar
[HRW92]Hwang, F. K., Richards, D. S., and Winter, P., The Steiner tree problem. Annals of Discrete Mathematics 53, North-Holland Publishing Co. (Amsterdem, 1992).Google Scholar
[Las86]Lassak, M., Covering a plane convex body by four homothetical copies with the smallest positive ratio. Geom. Dedicata 21 (1986), 155–167.CrossRefGoogle Scholar
[Las98]Lassak, M., Covering a three-dimensional convex body by smaller homothetic copies. Beiträge Algebra Geom. 39 (1998), 259–262.Google Scholar
[Lev54]Levi, F. W., Ein geometrisches Überdeckungsproblem. Arch. Math. 5 (1954), 476–478.CrossRefGoogle Scholar
[Mor92]Morgan, F., Minimal surfaces, crystals, shortest networks, and undergraduate research. Math. Intelligencer 14 (1992), 37–44.CrossRefGoogle Scholar
[Mor98]Morgan, F., Riemannian Geometry, a Beginner's Guide (2nd ed.). A. K. Peters Ltd. (Wellesley, MA, 1998). (1st ed., Jones and Bartlett, Boston, 1992).CrossRefGoogle Scholar
[MS99]Martini, H. and Soltan, V., Combinatorial problems on the illumination of convex bodies. Aequationes Math. 57 (1999), 121–152.CrossRefGoogle Scholar
[Rog57]Rogers, C. A., A note on coverings. Mathematika 4 (1957), 1–6.CrossRefGoogle Scholar
[RS57]Rogers, C. A. and Shephard, G. C., The difference body of a convex body. Arch. Math. 8 (1957), 220–233.CrossRefGoogle Scholar
[RZ97]Rogers, C. A. and Zong, C., Covering convex bodies by translates of convex bodies. Mathematika 44 (1997), 215–218.CrossRefGoogle Scholar
[Swa99]Swanepoel, K. J., Vertex degrees of Steiner minimal trees in and other smooth Minkowski spaces. Discrete Comput. Geom. 21 (1999), 437–447.CrossRefGoogle Scholar
[Swa00]Swanepoel, K. J., The local Steiner problem in normed planes. Networks 36 (2000), 104–113.3.0.CO;2-K>CrossRefGoogle Scholar
[Sza97]Szabó, L., Recent results on illumination problems. In Intuitive Geometry, Bolyai Soc. Math. Studies 6, János Bolyai Mathematical Society (Budapest, 1997), 207–221.Google Scholar
[Zon98]Zong, C., The kissing numbers of convex bodies—a brief survey. Bull. London Math. Soc. 30 (1998), 1–10.CrossRefGoogle Scholar