Combinatorial Geometry邓俊辉25September20261:18AM
Combinatorial Geometry 邓俊辉 25 September 20261:18 AM
Radon'sTheoremRadon'spartitionGivenP afamilyof sets in Ed,ifthere aretwo disjoint,non-empty subfamilies PandP2ofPsuchthatconv(P)conv(P2)+O,then(P1,P2)iscalledaRadonpartition ofPRadon's TheoremEveryfamilyofn≥d+2setsinEdadmitsaRadonpartitionJunhui Deng,Tsinghua Computer
Radon's Theorem ☞ Radon's partition − Given P a family of sets in E d , 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 E d admits a Radon partition Junhui Deng, Tsinghua Computer
Radon'o TheoremKirchberger'sTheoremForanyRadonpartition(P1P,)ofafamilyPofn≥d+2setsinEd,thereisasubfamilyUPwith(dim(P,UP2)+2)setssuchthat(PnU,P2nU)isaRadonpartitionofU(andhenceofP)Tverberg'sTheorem店0Everysetof (m-1)(d+1)+1pointsinEdcanbedividedintom(pairwisedisjoint)subsetswhoseconvexhullshaveacommonpoint;@thenumber(m-1)(d+1)+1isthesmallestwhichhasthestatedpropertyJunhui 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 E d , 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 E d 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
lelly'Theorem[Helly,1923][Finite version] Afamily offinite convex setsadmits a nonempty commonintersectioniffeachofits(d+1)-cardinalitysubfamiliesdoes[lnfiniteversion] Afamily of infinite compact convex sets admits a nonemptycommonintersectioniffeachofits(d+1)-cardinalitysubfamiliesdoesJunhui 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
Tranvera田k-TransversalGiven Fafamily of sets in Ed,ak-flat T is called ak-transversal of FifTmeetseverymemberofFExamplesO-transversal/Hellytheorem1-transversal/stabbinglineJunhui Deng,Tsinghua Computer
Transversal ☞ k-Transversal − Given F a family of sets in E d , 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