No-Dimensional Tverberg Partitions Revisited.
Saved in:
| Title: | No-Dimensional Tverberg Partitions Revisited. |
|---|---|
| Authors: | Har-Peled, Sariel1 (AUTHOR) sariel@illinois.edu, Robson, Eliot W.1 (AUTHOR) erobson2@illinois.edu |
| Source: | Discrete & Computational Geometry. Jun2026, Vol. 75 Issue 4, p1247-1265. 19p. |
| Subjects: | Deterministic algorithms, Algorithms, Monte Carlo method, Convex domains, Computational geometry, Geometric approach, Combinatorial geometry |
| Abstract: | Given a set P ⊂ R 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 / δ 2) , 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 (d n 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
Be the first to leave a comment!
