Abstract
Let V be a finite set of points in the Euclidean d-space (d ≧ 2). The intersection of all unit balls B(υ, 1) centered at υ, where υ 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 1950’s 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 \( \mathcal{B} \)(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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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.
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.
K. Bezdek and M. Naszódi, Rigidity of ball-polyhedra in Euclidean 3-space. European J. Combin., 27 (2006), 255–268.
B. Bollobás, The Art of Mathematics, Coffee Time in Memphis, Cambridge University Press (2006).
V. Boltyanski, H. Martini and P. Soltan, Excursions into Combinatorial Geometry, Springer (Berlin-Heidelberg, 1997).
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.
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.
V. L. Dol’nikov, Some properties of graphs of diameters, Discrete Comput. Geom., 24 (2000), 293–299.
H. G. Eggleston, Convexity, Cambridge University Press (1958).
H. G. Eggleston, Sets of constant width in finite dimensional Banach spaces, Israel J. Math., 3 (1965), 163–172.
P. Erdős, On sets of distances of n points. Amer. Math. Monthly, 53 (1946), 248–250.
P. Erdős, 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.
P. Erdős and J. Pach, Variations on the theme of repeated distances, Combinatorica, 10 (1990), 261–269.
B. Grünbaum, A proof of Vázsonyi’s conjecture, Bull. Research Council Israel, Section A, 6 (1956), 77–78.
B. Grünbaum, Convex Polytopes, Interscience Publishers (London-New York-Sydney, 1967) (completed version: Springer, 2003).
B. Grünbaum and G. C. Shephard, Is self-duality involutory? Amer. Math. Monthly, 95 (1988), 729–733.
A. Heppes, Beweis einer Vermutung von A. Vázsonyi, Acta Math. Acad. Sci. Hungar., 7 (1956), 463–466.
H. W. E. Jung, Über die kleinste Kugel, die eine räumliche Figur einschließt, J. Reine Angew. Math., 123 (1901), 241–257.
M. Katchalski and H. Last, On geometric graphs with no two edges in convex position, Discrete Comput. Geom., 19 (1998), 399–404.
J. Pach and P. K. Agarwal, Combinatorial Geometry, John Wiley & Sons (1995).
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.
Y. S. Kupitz, Extremal Problems of Combinatorial Geometry, Aarhus University, Lecture Notes Series, 53 (1979).
Y. S. Kupitz and H. Martini, On the weak circular intersection property, Studia Sci. Math. Hungar., 36 (2000), 371–385.
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).
Y. S. Kupitz, H. Martini and B. Wegner, A linear-time construction of Reuleaux polygons, Beiträge Algebra Geom., 37 (1996), 415–427.
A. E. Mayer, Eine Überkonvexität, Math. Z., 39 (1934), 512–531.
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.
A. Perlstein and R. Pinchasi, Generalized thrackles and geometric graphs in ℝ3 with no pair of strongly avoiding edges, Graphs Combin., 24 (2008), 373–389.
R. Pinchasi, Geometric graphs with no two parallel edges, Combinatorica, 28 (2008), 127–130.
G. T. Sallee, Reuleaux polytopes, Mathematika, 17 (1970), 315–323.
Z. Schur, M. A. Perles, H. Martini and Y. S. Kupitz, On the number of maximal regular simplices determined by n points in ℝd, in: Discrete and Computational Geometry — The Goodman-Pollack Festschrift, Springer (2003), pp. 767–787.
S. Straszewicz, Sur un probléme géométrique de P. Erdős, Bull. Acad. Polon. Sci. Cl. III, 5 (1957), 39–40, IV–V.
K. J. Swanepoel, A new proof of Vázsonyi’s conjecture, J. Combin. Theory, Ser A., 115 (2008), 888–892.
K. J. Swanepoel, Unit distances and diameters in Euclidean spaces, Discrete Comput. Geom., 41 (2009), 1–27.
P. Valtr, On geometric graphs with no k pairwise parallel edges, Discrete Comput. Geom., 19 (1998), 461–469.
P. van Wamelen, The maximum number of unit distances among n points in dimension four, Beiträge Algebra Geom., 40 (1990), 475–477.
D. R. Woodall, Thrackles and Deadlock, in: Combinatorics, Proc. Conf. Comb. Math. (D. Welsh, ed.), Academic Press (London, 1971), pp. 335–347.
I. M. Yaglom and V. Boltyanski, Convex Figures (transl. from Russian) (New York, 1961).
Author information
Authors and Affiliations
Corresponding author
Additional information
Partially supported by the Landau Center at the Mathematics Institute of the Hebrew University of Jerusalem Minerva Foundation, Germany, and by Deutsche Forschungsgemeinschaft.
Rights and permissions
About this article
Cite this article
Kupitz, Y.S., Martini, H. & Perles, M.A. Ball polytopes and the Vázsonyi problem. Acta Math Hung 126, 99–163 (2010). https://doi.org/10.1007/s10474-009-9030-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10474-009-9030-0
Key words and phrases
- 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 problem