DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2024.26

No-Dimensional Tverberg Partitions Revisited

Authors: Sariel Har-Peled and Eliot W. Robson

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract

Given a set P ⊂ ℝ^d of n points, with diameter Δ, and a parameter δ ∈ (0,1), it is known that there is a partition of P into sets P_1, …, P_t, each of size O(1/δ²), such that their convex hulls all intersect a common ball of radius δΔ. We prove that a random partition, with a simple alteration step, yields the desired partition, resulting in a (randomized) linear time algorithm (i.e., O(dn)). We also provide a deterministic algorithm with running time O(dn log n). Previous proofs were either existential (i.e., at least exponential time), or required much bigger sets. In addition, the algorithm and its proof of correctness are significantly simpler than previous work, and the constants are slightly better. We also include a number of applications and extensions using the same central ideas. For example, we provide a linear time algorithm for computing a "fuzzy" centerpoint, and prove a no-dimensional weak ε-net theorem with an improved constant.

Cite as

Sariel Har-Peled and Eliot W. Robson. No-Dimensional Tverberg Partitions Revisited. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.SWAT.2024.26,
  author =	{Har-Peled, Sariel and Robson, Eliot W.},
  title =	{{No-Dimensional Tverberg Partitions Revisited}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.26},
  URN =		{urn:nbn:de:0030-drops-200664},
  doi =		{10.4230/LIPIcs.SWAT.2024.26},
  annote =	{Keywords: Points, partitions, convex hull, high dimension}
}

Search Results

Documents authored by Robson, Eliot W.

No-Dimensional Tverberg Partitions Revisited

Abstract

Cite as

Thanks for your feedback!

Could not send message