Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A generalisation of Tverberg’s theorem
Soberón P., Strausz R. Discrete & Computational Geometry47 (3):455-460,2012.Type:Article
Date Reviewed: Dec 3 2012

Tverberg’s theorem is a result from discrete geometry, which states that, in any d-dimensional vector space for any set of (k-1)(d+1)+1 points in that vector space, the set can be partitioned into k disjoint subsets, the convex hulls of which are intersecting. The paper at hand generalizes this theorem by stating that, when considering a larger set of points (r + 1 additional points), a partition of k subsets can be found such that removing any given set of r points from each subset of the partition still yields the property that the convex hulls of the remaining sets are intersecting.

The paper starts with a short introduction to Tverberg’s theorem, its mathematical history, and previously discovered generalizations. In the following section, the authors present some mathematical definitions, notations, and the principal lemma used for proving the main theorem. The third section contains the proof of the generalized theorem and concludes with a conjecture that the number of points in the theorem is tight, that is, that taking even one more point away will cause the theorem to not work. The last section is a remark on the proof technique, illustrating that the lemma of the second section is indeed necessary because an extension of the Bárány-Lováz theorem, usually used in the proof, would not work.

This very short paper would be understandable to most readers only with additional background reading. It would have been nice to have some examples illustrating the content of the theorem for the two-dimensional case. Furthermore, several other theorems are referenced but not described in the paper. This may be sufficient for a specialist in the field with ready access to the relevant literature, but leaves less specialized readers without enough information. From a computer science perspective, it would also be nice to know how to compute the respective partitions from a set of points. It is very hard to extract the algorithm from the proofs.

Reviewer:  Markus Wolf Review #: CR140710 (1303-0248)
Bookmark and Share
 
Geometrical Problems And Computations (F.2.2 ... )
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
 
Discrete Mathematics (G.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Geometrical Problems And Computations": Date
Some performance tests of convex hull algorithms
Allison D., Noga M. BIT 24(1): 2-13, 1984. Type: Article
Feb 1 1985
A fast voronoi-diagram algorithm with quaternary tree bucketing
Ohya T., Iri M., Murota K. Information Processing Letters 18(4): 227-231, 1984. Type: Article
Jan 1 1985
Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm
Chazelle B. (ed) SIAM Journal on Computing 13(3): 488-507, 1984. Type: Article
Mar 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy