Télécharger la présentation
## Combinatorial Geometry

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Combinatorial Geometry**邓俊辉 清华大学计算机系 deng@tsinghua.edu.cn http://vis.cs.tsinghua.edu.cn:10020/~deng 2014年9月27日星期六下午7时44分**Radon's Theorem**• Radon's partition • Given P a family of sets in Ed, if there are two disjoint, non-empty subfamilies P1 and P2 of P such that conv(P1) conv(P2) , then (P1, P2) is called a Radon partition of P • Radon's Theorem • Every family of n d+2 sets in Ed admits a Radon partition Junhui Deng, Tsinghua Computer**Radon's Theorem**• Kirchberger's Theorem • For any Radon partition (P1, P2) of a family P of n d+2 sets in Ed, there is a subfamily U P with (dim(P1P2)+2) sets such that (P1U, P2U) is a Radon partition of U (and hence of P) • Tverberg's Theorem • Every set of (m-1)(d+1)+1 points in Ed can be divided into m (pairwise disjoint) subsets whose convex hulls have a common point; • the number (m-1)(d+1)+1 is the smallest which has the stated property Junhui Deng, Tsinghua Computer**Helly's Theorem**• [Helly, 1923] • [Finite version] A family of finite convex sets admits a nonempty common intersection iff each of its (d+1)-cardinality subfamilies does • [Infinite version] A family of infinite compact convex sets admits a nonempty common intersection iff each of its (d+1)-cardinality subfamilies does Junhui Deng, Tsinghua Computer**Transversal**• k-Transversal • Given F a family of sets in Ed, a k-flat T is called a k-transversal of F if • T meets every member of F • Examples • 0-transversal / Helly theorem • 1-transversal / stabbing line Junhui Deng, Tsinghua Computer**The space of k-transversals**• Given F a family of convex sets in Ed • the topological space of all k-flats intersecting F is called the space of k-transversals of F • The space of 0-transversals • convex (why?) • The space of k-transversals (k>=1) • not convex • even not connected Junhui Deng, Tsinghua Computer**Finding k-Transversal**• Goal • not just a single k-transversal • a data structure representing the entire space of k-transversals • Problems • How much time/space is needed for the construction? • What's the complexity of such a data structure? • What's the combinatorial complexity of this space? Junhui Deng, Tsinghua Computer**Ham-Sandwich Theorem**• [Discrete version] • Let P1, …, Pd be d finite sets of points in Ed • There exists a hyperplane h that simultaneously bisects P1, …, Pd Junhui Deng, Tsinghua Computer**Minkowski's first Theorem**• [Minkowski, 1891] • Let C Ed be symmetric, convex, bounded, and suppose that vol(C) > 2d • Then C contains at least one lattice point different from 0 • Ex: Regular Forest • Diameter of forest = 26m • Diameter of trees = ? ? Junhui Deng, Tsinghua Computer**Two-Square Theorem & Four-Square Theorem**• [Two-square Theorem] • Each prime p 1 (mod 4) can be written as a sum of two squares • i.e., prime p = 4k + 1, a, b Z s.t. p = a2 + b2 • e.g. • 13 = 22 + 32 • 17 = 12 + 42 • [Four-square Theorem] • Any natural number can be written as a sum of 4 squares of integer Junhui Deng, Tsinghua Computer**Four-Square Theorem**• 2004 • = (25, 25, 23, 15) = (27, 25, 19, 17) = (27, 25, 23, 11) = (27, 25, 25, 5) = (28, 26, 20, 12) • = (28, 28, 20, 6) = (29, 21, 19, 19) = (29, 25, 23, 3) = (30, 28, 16, 8) = (31, 23, 17, 15) • = (31, 27, 17, 5) = (31, 29, 11, 9) = (31, 31, 9, 1) = (32, 20, 18, 16) = (32, 24, 20, 2) • = (32, 28, 14, 0) = (32, 30, 8, 4) = (33, 23, 19, 5) = (33, 25, 13, 11) = (33, 25, 17, 1) • = (33, 29, 7, 5) = (34, 24, 16, 4) = (34, 28, 8, 0) = (35, 21, 13, 13) = (35, 21, 17, 7) • = (35, 23, 13, 9) = (35, 23, 15, 5) = (35, 27, 5, 5) = (35, 27, 7, 1) = (36, 16, 16, 14) • = (36, 26, 4, 4) = (37, 17, 15, 11) = (37, 19, 15, 7) = (37, 21, 13, 5) = (37, 23, 9, 5) • = (37, 25, 3, 1) = (38, 20, 12, 4) = (39, 17, 13, 5) = (39, 19, 11, 1) = (40, 14, 12, 8) • = (40, 16, 12, 2) = (40, 18, 8, 4) = (40, 20, 2, 0) = (41, 11, 11, 9) = (41, 15, 7, 7) • = (41, 17, 5, 3) = (43, 9, 7, 5) = (43, 11, 5, 3) = (44, 6, 4, 4) = (44, 8, 2, 0) Junhui Deng, Tsinghua Computer**The Erdos-Szekeres Theorem**• Convex Independent Set • A set X Rd is called convex independent if • for every x X, we have x conv(X\{x}) • [Erdos & Szekeres, 1935] • For every k N, there exists a number n(k) such that • any n(k)-point set X R2in general position • contains a k-point convex independent subset • What is the lower bound of n(k)? • Ex: n(5) 9 Junhui Deng, Tsinghua Computer**The k-Set Problem**• k-Sets • Let P be a configuration of n points in Ed and let S be a halfspace • PS is called a k-set of P if card(PS) = k, 0 k n • Problems • What are the upper/lower bounds for the maximum number of k-sets for all configurations of n points in Ed, in terms of n and k? • What are the upper/lower bounds for the maximum number of k-sets for all configurations of n points in E2, in terms of n and k? Junhui Deng, Tsinghua Computer**The k-Set Problem**• Lower bounds • (nlog(k+1)) Edelsbrunner & Welzl, 1985 • (nesqrt(log(k+1))) Toth, 1999 • Upper bounds • O(n*sqrt(k+1)) Lovasz, 1971 • O(n*sqrt(k+1)/log*(k+1)) Pach et al., 1989 • O(n*cbrt(k+1)) Dey, 1998 Junhui Deng, Tsinghua Computer