Ball polytopes and the Vázsonyi problem. (English) Zbl 1224.52025
Authors’ abstract: Let \(V\) be a finite set of points in the Euclidean \(d\)-space \((d\geqq 2)\). The intersection of all unit balls \(B(u, 1)\) centered at \(u\), where \(u\) ranges over \(V\), henceforth denoted by \(\mathcal B(V)\) is the ball polytope associated with \(V\). After some preparatory discussion on spherical convexity and spindle convexity, the paper focuses on two central themes.
(a) Define the boundary complex of \(\mathcal B(V)\), i.e., define its vertices, edges and facets in dimension 3, and investigate its basic properties.
(b) Apply results of this investigation to characterize finite sets of diameter 1 in the (Euclidean) 3-space for which the diameter is attained a maximal number of times as a segment (of length 1) with both endpoints in \(V\). A basic result for such a characterization goes back to Grünbaum, Heppes and Straszewicz, who proved independently of each other, in the late 1950s by means of ball polytopes, that the diameter of \(V\) is attained at most \(2| V| -2\) times. Call \(V\) extremal if its diameter is attained this maximal number \((2| V| - 2)\) of times. We extend the aforementioned result by showing that \(V\) is extremal iff \(V\) coincides with the set of vertices of its ball polytope \(\mathcal B(V)\) and show that in this case the boundary complex of \(V\) is self-dual in some strong sense. The problem of constructing new types of extremal configurations is not addressed in this paper, but we do present here some such new types.
(a) Define the boundary complex of \(\mathcal B(V)\), i.e., define its vertices, edges and facets in dimension 3, and investigate its basic properties.
(b) Apply results of this investigation to characterize finite sets of diameter 1 in the (Euclidean) 3-space for which the diameter is attained a maximal number of times as a segment (of length 1) with both endpoints in \(V\). A basic result for such a characterization goes back to Grünbaum, Heppes and Straszewicz, who proved independently of each other, in the late 1950s by means of ball polytopes, that the diameter of \(V\) is attained at most \(2| V| -2\) times. Call \(V\) extremal if its diameter is attained this maximal number \((2| V| - 2)\) of times. We extend the aforementioned result by showing that \(V\) is extremal iff \(V\) coincides with the set of vertices of its ball polytope \(\mathcal B(V)\) and show that in this case the boundary complex of \(V\) is self-dual in some strong sense. The problem of constructing new types of extremal configurations is not addressed in this paper, but we do present here some such new types.
Reviewer: Ágota H. Temesvári (Sopron)
MSC:
| 52C10 | Erdős problems and related topics of discrete geometry |
| 52A30 | Variants of convex sets (star-shaped, (\(m, n\))-convex, etc.) |
| 52B10 | Three-dimensional polytopes |
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
| 52A40 | Inequalities and extremum problems involving convexity in convex geometry |
Keywords:
ball hull; ball polytope; barycentric subdivision; canonical self-duality; diameter graph; face complex; face structure; generalized convexity notion; geometric graph; involutory self-duality; Reuleaux polytope; spherical convexity; spindle convexity; Vázsonyi problemReferences:
| [1] | J. Ashley, B. Grünbaum, G. C. Shephard and W. Stromquist, Self-duality groups and ranks of self-duality, in: Applied Geometry and Discrete Mathematics – The Victor Klee Festschrift (eds.: P. Gritzmann and B. Sturmfels), DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 4 (1991), 11–50. · Zbl 0752.52003 |
| [2] | K. Bezdek, Z. Langi, M. Naszódi and P. Papez, Ball-polyhedra, Discrete Comput. Geom., Special issue dedicated to the memory of László Fejes Tóth, 38 (2007), 201–230. · Zbl 1133.52001 · doi:10.1007/s00454-007-1334-7 |
| [3] | K. Bezdek and M. Naszódi, Rigidity of ball-polyhedra in Euclidean 3-space. European J. Combin., 27 (2006), 255–268. · Zbl 1089.52010 · doi:10.1016/j.ejc.2004.08.007 |
| [4] | B. Bollobás, The Art of Mathematics, Coffee Time in Memphis, Cambridge University Press (2006). · Zbl 1238.00002 |
| [5] | V. Boltyanski, H. Martini and P. Soltan, Excursions into Combinatorial Geometry, Springer (Berlin-Heidelberg, 1997). · Zbl 0877.52001 |
| [6] | P. Brass, On the maximum number of unit distances among n points in dimension four, in: Intuitive Geometry (eds.: I. Bárány et al.), Bolyai Soc. Math. Studies 4 (1997), pp. 277–290. · Zbl 0885.52015 |
| [7] | G. D. Chakerian and H. Groemer, Convex bodies of constant width, in: Convexity and its Applications (eds. P. M. Gruber and J. M. Wills), Birkhäuser (Basel, 1983), pp. 49–96. · Zbl 0518.52002 |
| [8] | V. L. Dol’nikov, Some properties of graphs of diameters, Discrete Comput. Geom., 24 (2000), 293–299. · Zbl 0965.05063 · doi:10.1007/s004540010036 |
| [9] | H. G. Eggleston, Convexity, Cambridge University Press (1958). |
| [10] | H. G. Eggleston, Sets of constant width in finite dimensional Banach spaces, Israel J. Math., 3 (1965), 163–172. · Zbl 0166.17901 · doi:10.1007/BF02759749 |
| [11] | P. Erdos, On sets of distances of n points. Amer. Math. Monthly, 53 (1946), 248–250. · Zbl 0060.34805 · doi:10.2307/2305092 |
| [12] | P. Erdos, On sets of distances of n points in Euclidean space, Magyar Tudom. Akad. Matem. Kut. Int. Közl. (Publ. Math. Inst. Hung. Acad. Sci.), 5 (1960), 165–169. |
| [13] | P. Erdos and J. Pach, Variations on the theme of repeated distances, Combinatorica, 10 (1990), 261–269. · Zbl 0722.52009 · doi:10.1007/BF02122780 |
| [14] | B. Grünbaum, A proof of Vázsonyi’s conjecture, Bull. Research Council Israel, Section A, 6 (1956), 77–78. |
| [15] | B. Grünbaum, Convex Polytopes, Interscience Publishers (London-New York-Sydney, 1967) (completed version: Springer, 2003). · Zbl 0163.16603 |
| [16] | B. Grünbaum and G. C. Shephard, Is self-duality involutory? Amer. Math. Monthly, 95 (1988), 729–733. · Zbl 0658.52004 · doi:10.2307/2322253 |
| [17] | A. Heppes, Beweis einer Vermutung von A. Vázsonyi, Acta Math. Acad. Sci. Hungar., 7 (1956), 463–466. · doi:10.1007/BF02020540 |
| [18] | H. W. E. Jung, Über die kleinste Kugel, die eine räumliche Figur einschließt, J. Reine Angew. Math., 123 (1901), 241–257. · JFM 32.0296.05 · doi:10.1515/crll.1901.123.241 |
| [19] | M. Katchalski and H. Last, On geometric graphs with no two edges in convex position, Discrete Comput. Geom., 19 (1998), 399–404. · Zbl 0908.05033 · doi:10.1007/PL00009357 |
| [20] | J. Pach and P. K. Agarwal, Combinatorial Geometry, John Wiley & Sons (1995). |
| [21] | Y. S. Kupitz, On pairs of disjoint segments in convex position in the plane, in: Convexity and Graph Theory (Jerusalem, 1981), North-Holland Math. Stud., 87, North-Holland (1984), pp. 203–208. · doi:10.1016/S0304-0208(08)72827-5 |
| [22] | Y. S. Kupitz, Extremal Problems of Combinatorial Geometry, Aarhus University, Lecture Notes Series, 53 (1979). |
| [23] | Y. S. Kupitz and H. Martini, On the weak circular intersection property, Studia Sci. Math. Hungar., 36 (2000), 371–385. · Zbl 0980.52001 |
| [24] | Y. S. Kupitz, H. Martini and M. A. Perles, Finite sets in Rd with many diameters – a survey, in: Proceedings of the International Conference on Mathematics and Applications (ICMA-MU 2005, Bangkok), Mahidol University Press (Bangkok, 2005), pp. 91–112. Reprinted in a special volume of the East-West J. Math.: Contributions in Mathematics and Applications (2007), 41–57 (Zbl. 1141.51300). · Zbl 1141.51300 |
| [25] | Y. S. Kupitz, H. Martini and B. Wegner, A linear-time construction of Reuleaux polygons, Beiträge Algebra Geom., 37 (1996), 415–427. · Zbl 0876.52002 |
| [26] | A. E. Mayer, Eine Überkonvexität, Math. Z., 39 (1934), 512–531. |
| [27] | C. C. Neaderhauser and G. B. Purdy, On finite sets in E k in which the diameter is frequently achieved, Period. Math. Hungar., 13 (1982), 253–257. · doi:10.1007/BF01847922 |
| [28] | A. Perlstein and R. Pinchasi, Generalized thrackles and geometric graphs in \(\mathbb{R}\)3 with no pair of strongly avoiding edges, Graphs Combin., 24 (2008), 373–389. · Zbl 1188.05055 · doi:10.1007/s00373-008-0796-6 |
| [29] | R. Pinchasi, Geometric graphs with no two parallel edges, Combinatorica, 28 (2008), 127–130. · Zbl 1164.05015 · doi:10.1007/s00493-008-2250-z |
| [30] | G. T. Sallee, Reuleaux polytopes, Mathematika, 17 (1970), 315–323. · Zbl 0218.52001 · doi:10.1112/S0025579300002977 |
| [31] | Z. Schur, M. A. Perles, H. Martini and Y. S. Kupitz, On the number of maximal regular simplices determined by n points in \(\mathbb{R}\)d, in: Discrete and Computational Geometry – The Goodman-Pollack Festschrift, Springer (2003), pp. 767–787. · Zbl 1081.52016 |
| [32] | S. Straszewicz, Sur un probléme géométrique de P. Erdos, Bull. Acad. Polon. Sci. Cl. III, 5 (1957), 39–40, IV–V. · Zbl 0077.14204 |
| [33] | K. J. Swanepoel, A new proof of Vázsonyi’s conjecture, J. Combin. Theory, Ser A., 115 (2008), 888–892. · Zbl 1226.05184 · doi:10.1016/j.jcta.2007.08.006 |
| [34] | K. J. Swanepoel, Unit distances and diameters in Euclidean spaces, Discrete Comput. Geom., 41 (2009), 1–27. · Zbl 1162.52010 · doi:10.1007/s00454-008-9082-x |
| [35] | P. Valtr, On geometric graphs with no k pairwise parallel edges, Discrete Comput. Geom., 19 (1998), 461–469. · Zbl 0908.05035 · doi:10.1007/PL00009364 |
| [36] | P. van Wamelen, The maximum number of unit distances among n points in dimension four, Beiträge Algebra Geom., 40 (1990), 475–477. · Zbl 0962.52002 |
| [37] | D. R. Woodall, Thrackles and Deadlock, in: Combinatorics, Proc. Conf. Comb. Math. (D. Welsh, ed.), Academic Press (London, 1971), pp. 335–347. |
| [38] | I. M. Yaglom and V. Boltyanski, Convex Figures (transl. from Russian) (New York, 1961). · Zbl 0098.35501 |
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.
