DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2025.43

On Spheres with k Points Inside

Authors: Herbert Edelsbrunner, Alexey Garber, and Morteza Saghafian

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

We generalize a classical result by Boris Delaunay that introduced Delaunay triangulations. In particular, we prove that for a locally finite and coarsely dense generic point set A in ℝ^d, every generic point of ℝ^d belongs to exactly binom(d+k,d) simplices whose vertices belong to A and whose circumspheres enclose exactly k points of A. We extend this result to the cases in which the points are weighted, and when A contains only finitely many points in ℝ^d or in 𝕊^d. Furthermore, we use the result to give a new geometric proof for the fact that volumes of hypersimplices are Eulerian numbers.

Cite as

Herbert Edelsbrunner, Alexey Garber, and Morteza Saghafian. On Spheres with k Points Inside. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 43:1-43:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{edelsbrunner_et_al:LIPIcs.SoCG.2025.43,
  author =	{Edelsbrunner, Herbert and Garber, Alexey and Saghafian, Morteza},
  title =	{{On Spheres with k Points Inside}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{43:1--43:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.43},
  URN =		{urn:nbn:de:0030-drops-231951},
  doi =		{10.4230/LIPIcs.SoCG.2025.43},
  annote =	{Keywords: Triangulations, higher-order Delaunay triangulations, hypertriangulations, Delone sets, k-sets, Worpitzky’s identity, hypersimplices}
}

Search Results

Documents authored by Garber, Alexey

On Spheres with k Points Inside

Abstract

Cite as

Thanks for your feedback!

Could not send message