2009/05/11 by Yaakov S. Kupitz, Kupitz, Yaakov S., Horst Martini +3 · 1 citation
Computer Science · Mathematics · #05C62 #52A30 #52A40 #52B05 #52B10 #52C10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG) #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.0905.1528
openalex publication_date 2009/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let V be a finite set of points in Euclidean d-space (d >= 2). The intersection of all unit balls B(v,1) centered at v, where v ranges over V, henceforth denoted by B(V) is the ball polytope associated with V. Note that B(V) is non-empty iff the circumradius of V is <= 1. After some preparatory discussion on spherical convexity and spindle convexity, the paper focuses on two central themes. [a] Define the boundary complex of B(V) (assuming it is non-empty, of course), i.e., define its vertices, edges and facets in dimension 3 (in dimension 2 this complex is just a circuit), and investigate its basic properties. [b] Apply results of this investigation to characterize finite sets of diameter 1 in (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 Grunbaum, Heppes and Straszewicz, who proved independently that the diameter of V is attained at most 2|V|-2 times, thus affirming a conjecture of Vazsonyi from circa 1935. Call V extremal if its diameter is attained this maximal number (2|V|-2) of times. We extend the aforementioned basic result by showing that V is extremal iff V coincides with the set of vertices of its ball polytope B(V) and show that in this case the boundary complex of B(V) is self-dual in some strong sense. For the sake of priority we mention that, in the present form (except for a few changes in the footnotes), the paper was submitted to a journal already in February 1, 2008.