View in EDS HTML Full Text PDF Full Text

No-Dimensional Tverberg Partitions Revisited.

Saved in:
Bibliographic Details
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.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 194162863
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: No-Dimensional Tverberg Partitions Revisited.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Har-Peled%2C+Sariel%22">Har-Peled, Sariel</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> sariel@illinois.edu</i><br /><searchLink fieldCode="AR" term="%22Robson%2C+Eliot+W%2E%22">Robson, Eliot W.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> erobson2@illinois.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Discrete+%26+Computational+Geometry%22">Discrete & Computational Geometry</searchLink>. Jun2026, Vol. 75 Issue 4, p1247-1265. 19p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Deterministic+algorithms%22">Deterministic algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Monte+Carlo+method%22">Monte Carlo method</searchLink><br /><searchLink fieldCode="DE" term="%22Convex+domains%22">Convex domains</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+geometry%22">Computational geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Geometric+approach%22">Geometric approach</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorial+geometry%22">Combinatorial geometry</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=194162863
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00454-025-00725-6
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 19
        StartPage: 1247
    Subjects:
      – SubjectFull: Deterministic algorithms
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Monte Carlo method
        Type: general
      – SubjectFull: Convex domains
        Type: general
      – SubjectFull: Computational geometry
        Type: general
      – SubjectFull: Geometric approach
        Type: general
      – SubjectFull: Combinatorial geometry
        Type: general
    Titles:
      – TitleFull: No-Dimensional Tverberg Partitions Revisited.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Har-Peled, Sariel
      – PersonEntity:
          Name:
            NameFull: Robson, Eliot W.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 06
              Text: Jun2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 01795376
          Numbering:
            – Type: volume
              Value: 75
            – Type: issue
              Value: 4
          Titles:
            – TitleFull: Discrete & Computational Geometry
              Type: main
ResultId 1