65:
1714: + 1 of the points; that is, that the given point is part of a Radon partition in which it is a singleton. One proof of Carathéodory's theorem uses a technique of examining solutions to systems of linear equations, similar to the proof of Radon's theorem, to eliminate one point at a time until at most
68:
Two sets of four points in the plane (the vertices of a square and an equilateral triangle with its centroid), the multipliers solving the system of three linear equations for these points, and the Radon partitions formed by separating the points with positive multipliers from the points with
1785:
connecting a pair of vertices in the set. With this definition, every set of ω + 1 vertices in the graph can be partitioned into two subsets whose convex hulls intersect, and ω + 1 is the minimum number for which this is possible, where ω is the
641:
81:
can be partitioned in one of two ways. It may form a triple and a singleton, where the convex hull of the triple (a triangle) contains the singleton; alternatively, it may form two pairs of points that form the endpoints of two intersecting
335:
184:
745:
348: + 1 equations that they must satisfy (one for each coordinate of the points, together with a final equation requiring the sum of the multipliers to be zero). Fix some particular nonzero solution
1562: + 1 points (for instance, the points of a regular simplex) such that every two nonempty subsets can be separated from each other by a hyperplane. However, no matter which set of
1086:
1017:
952:
1608:
of a set of points is the point minimizing the sum of distances to the points in the set; it generalizes the one-dimensional median and has been studied both from the point of view of
1512:
1461:
1415:
1369:
1692:
512:
421:
389:
1311:
2059:
832:
812:
792:
768:
504:
484:
461:
441:
2407:
1566: + 2 points is given, the two subsets of a Radon partition cannot be linearly separated. Therefore, the VC dimension of this system is exactly
1705:
220:
2437:
2353:
2327:
1934:
97:
2452:
2343:
1949:
2442:
879:
They are equivalent because any affine function on a simplex is uniquely determined by the images of its vertices. Formally, let Ć’ be an
652:
1728:, families of finite sets with the properties that the intersection of any two sets in the family remains in the family, and that the
2357:
1756:
by analogy to their definitions for convex sets in
Euclidean spaces, and it can be shown that these numbers satisfy the inequalities
1987:
2296:
2335:
2244:
1939:
1232:
must then be two disjoint faces whose images have a nonempty intersection. This same general statement, when applied to a
1710:
states that any point in the convex hull of some set of points is also within the convex hull of a subset of at most
1313:, which is a continuous function from S to R. The theorem says that, for any such function, there exists some point
2105:
212:
1547:
on intersections of convex sets; this proof was the motivation for Radon's original discovery of Radon's theorem.
1609:
1026:
957:
892:
1284:
1237:
2191:
1732:
and the union of all the sets belongs to the family. In this more general context, the convex hull of a set
1582:
1470:
The topological Radon theorem follows from the following more general theorem. For any simplicial complex
1589:
of any point set, in an amount of time that is polynomial in both the number of points and the dimension.
1586:
2447:
2373:
2136:
1635:
837:
This proof method allows for the efficient construction of a Radon point, in an amount of time that is
636:{\displaystyle p=\sum _{x_{i}\in I}{\frac {a_{i}}{A}}x_{i}=\sum _{x_{j}\in J}{\frac {-a_{j}}{A}}x_{j},}
1887:"A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs"
1482:
1431:
1385:
1339:
1961:
1574:
842:
1641:
394:
2183:
1175:
368:
2390:
2292:"Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers"
2153:
2122:
1916:
1867:
1748:
points have two subsets whose convex hulls intersect. Similarly, one can define the Helly number
1248:
The topological Radon theorem was originally proved by
Bajmoczy and Barany in the following way:
771:
46:
2232:
1544:
16:
Says d+2 points in d dimensions can be partitioned into two subsets whose convex hulls intersect
2339:
2100:
1983:
1957:
1945:
1908:
1886:
1859:
1613:
1421:
1290:
1616:. For sets of four points in the plane, the geometric median coincides with the Radon point.
2416:
2382:
2359:
Using the Borsuk–Ulam
Theorem: Lectures on Topological Methods in Combinatorics and Geometry
2305:
2262:
2211:
2145:
2114:
2030:
2022:
1977:
1898:
1851:
1779:
1775:
1605:
1537:
2319:
2223:
1324:
to the same point of R. This implies that the images of these two disjoint faces intersect.
463:
form the required partition of the points into two subsets with intersecting convex hulls.
2315:
2219:
2034:
880:
858:
838:
78:
2008:"Four-point Fermat location problems revisited. New proofs and extensions of old results"
2007:
2402:
2195:
2187:
2003:
1627:
817:
797:
777:
753:
489:
469:
446:
426:
1204: + 1)-dimensional compact convex set, and Ć’ is any continuous function from
2431:
2394:
2267:
2157:
1791:
1787:
1328:
Another proof was given by Lovasz and
Schrijver. A third proof is given by Matousek:
2126:
1871:
845:
or other efficient algorithms to solve the system of equations for the multipliers.
2368:
2199:
2165:
Chepoi, V. D. (1986), "Some properties of the d-convexity in triangulated graphs",
1920:
1551:
1372:
83:
32:
1903:
64:
2291:
1320:
The points g(y) and g(-y) are on two disjoint faces of Δ, and they are mapped by
2236:
1725:
1233:
1228:
is a simplex, the two simplex faces formed by the maximum and minimum points of
1224:
achieves its minimum value are mapped by Ć’ to the same point. In the case where
1188:
885:
871:
794:, and the right hand side expresses it as a convex combination of the points in
50:
41:
2420:
2215:
1782:
28:
1912:
1863:
330:{\displaystyle \sum _{i=1}^{d+2}a_{i}x_{i}=0,\quad \sum _{i=1}^{d+2}a_{i}=0,}
2310:
2253:
Duchet, Pierre (1987), "Convex sets in graphs. II. Minimal path convexity",
2026:
1729:
1558:-dimensional points with respect to linear separations. There exist sets of
1600:. The Radon point of three points in a one-dimensional space is just their
1778:, one may define a convex set to be a set of vertices that includes every
2371:(1921), "Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten",
1257:
20:
1192:, then there are two disjoint faces of Δ whose images under ƒ intersect.
875:, then there are two disjoint faces of Δ whose images under ƒ intersect.
179:{\displaystyle X=\{x_{1},x_{2},\dots ,x_{d+2}\}\subset \mathbf {R} ^{d}}
2386:
2149:
2118:
1855:
1240:, that Ć’ must map two opposite points of the sphere to the same point.
1183:
866:
2134:
Bandelt, H.-J.; Pesch, E. (1989), "A Radon theorem for Helly graphs",
423:
be the set of points with multipliers that are negative or zero. Then
1979:
Shortest
Connectivity: An Introduction with Applications in Phylogeny
1839:
1601:
1581: + 2 points by their Radon point can be used to compute an
1540:, the point that minimizes the sum of distances to the other points.
2280:
Eckhoff, J. (1993), "Helly, Radon, and Carathéodory type theorems",
1724:. Concepts related to Radon's theorem have also been considered for
2103:(1979), "A common generalization of Borsuk's and Radon's theorem",
1702:
subsets whose convex hulls intersect in at least one common point.
740:{\displaystyle A=\sum _{x_{i}\in I}a_{i}=-\sum _{x_{j}\in J}a_{j}.}
2204:
International
Journal of Computational Geometry & Applications
1982:, Combinatorial Optimization, vol. 17, Springer, p. 6,
1820:
1942:: Lectures on Topological Methods in Combinatorics and Geometry
57:
A point in the intersection of these convex hulls is called a
2284:, vol. A, B, Amsterdam: North-Holland, pp. 389–448
1840:"On a common generalization of Borsuk's and Radon's theorem"
194:-dimensional space. Then there exists a set of multipliers
2356:(2003), "5.1 Nonembeddability Theorems: An Introduction",
1536:
The Radon point of any four points in the plane is their
2200:"Approximating center points with iterated Radon points"
1543:
Radon's theorem forms a key step of a standard proof of
1212:-dimensional space, then there exists a linear function
391:
be the set of points with positive multipliers, and let
1736:
is the intersection of the family members that contain
1170:
to be any continuous function - not necessarily affine:
1158:. These two faces are disjoint, and their images under
1220:
achieves its maximum value and some other point where
1644:
1485:
1434:
1388:
1342:
1293:
1029:
960:
895:
820:
800:
780:
756:
655:
515:
492:
472:
449:
429:
397:
371:
223:
100:
1944:(2nd ed.). Berlin-Heidelberg: Springer-Verlag.
1162:
intersect - as claimed by the new formulation. The
1088:
can be partitioned into two disjoint subsets, e.g. (
834:
belongs to both convex hulls, completing the proof.
506:
must intersect, because they both contain the point
344: + 2 unknowns (the multipliers) but only
1790:of the given graph. For related results involving
1740:, and the Radon number of a space is the smallest
1686:
1550:Radon's theorem can also be used to calculate the
1506:
1455:
1409:
1363:
1305:
1147:is the image of the face spanned by the vertices (
1125:is the image of the face spanned by the vertices (
1080:
1011:
946:
826:
806:
786:
762:
739:
635:
498:
478:
455:
435:
415:
383:
329:
178:
2338:, vol. 212, Springer-Verlag, pp. 9–12,
2330:(2002), "1.3 Radon's Lemma and Helly's Theorem",
1844:Acta Mathematica Academiae Scientiarum Hungaricae
1891:Proceedings of the American Mathematical Society
853:An equivalent formulation of Radon's theorem is:
2405:(1966), "A generalization of Radon's theorem",
77: = 2, any set of four points in the
2239:(1963), "Helly's theorem and its relatives",
1885:Lovász, László; Schrijver, Alexander (1998).
1523:|| to R, the images of two disjoint faces of
8:
2273:
2176:
1799:
158:
107:
1519:, then for every continuous mapping from ||
2408:Journal of the London Mathematical Society
2062:, Lecture Notes by Marco Pellegrini, 2004.
1838:Bajmóczy, E. G.; Bárány, I. (1979-09-01).
1081:{\displaystyle x_{1},x_{2},\dots ,x_{d+2}}
1012:{\displaystyle x_{1},x_{2},\dots ,x_{d+2}}
947:{\displaystyle v_{1},v_{2},\dots ,v_{d+2}}
2309:
2290:Kay, David C.; Womble, Eugene W. (1971),
2266:
2255:Journal of Combinatorial Theory, Series A
2071:
1902:
1643:
1495:
1490:
1484:
1444:
1439:
1433:
1398:
1393:
1387:
1352:
1347:
1341:
1292:
1066:
1047:
1034:
1028:
997:
978:
965:
959:
932:
913:
900:
894:
819:
799:
779:
755:
728:
710:
705:
689:
671:
666:
654:
624:
608:
598:
584:
579:
566:
551:
545:
531:
526:
514:
491:
471:
448:
428:
396:
370:
312:
296:
285:
265:
255:
239:
228:
222:
211:, not all of which are zero, solving the
170:
165:
146:
127:
114:
99:
2047:
1631:
1166:generalizes this formluation. It allows
63:
2243:, Proc. Symp. Pure Math., vol. 7,
1816:
1814:
1810:
407:
2083:
1795:
1622:. A generalization for partition into
1110:with overlapping convex hull. Because
750:The left hand side of the formula for
2015:IMA Journal of Management Mathematics
39:Any set of d + 2 points in
7:
1833:
1831:
1829:
1136:, and similarly the convex hull of (
1317:on S, such that f(g(y)) = f(g(-y)).
1023:. By the original formulation, the
1698:-space, there is a partition into
1491:
1440:
1394:
1348:
1280:) are on two disjoint faces of Δ.
1260:) to Δ, such that for every point
14:
2362:, Springer-Verlag, pp. 88–92
1577:that repeatedly replaces sets of
1638:. It states that for any set of
1507:{\displaystyle K_{\Delta }^{*2}}
1456:{\displaystyle K_{\Delta }^{*2}}
1417:is homeomorphic to the sphere S.
1410:{\displaystyle K_{\Delta }^{*2}}
1364:{\displaystyle K_{\Delta }^{*2}}
1236:instead of a simplex, gives the
166:
1114:is affine, the convex hull of (
280:
2297:Pacific Journal of Mathematics
1687:{\displaystyle (d+1)(r-1)+1\ }
1672:
1660:
1657:
1645:
954:be the vertices of Δ, and let
416:{\displaystyle J=X\setminus I}
1:
2438:Theorems in discrete geometry
2336:Graduate Texts in Mathematics
2332:Lectures on Discrete Geometry
2245:American Mathematical Society
2060:Epsilon-nets and VC-dimension
1940:Using the Borsuk-Ulam Theorem
1904:10.1090/S0002-9939-98-04244-0
1794:instead of induced paths see
1382:The geometric realization of
2453:Geometric transversal theory
2268:10.1016/0095-8956(88)90039-1
1956:Written in cooperation with
1752:and the Carathéodory number
1182: + 1)-dimensional
865: + 1)-dimensional
384:{\displaystyle I\subseteq X}
2443:Theorems in convex geometry
2282:Handbook of Convex Geometry
1252:Construct a continuous map
1216:such that some point where
841:in the dimension, by using
2469:
2274:Bandelt & Pesch (1989)
2177:Bandelt & Pesch (1989)
2106:Acta Mathematica Hungarica
1800:Bandelt & Pesch (1989)
1336:be the simplex Δ, and let
1256:from S (the d-dimensional
770:expresses this point as a
213:system of linear equations
2216:10.1142/s021819599600023x
1976:Cieslik, Dietmar (2006),
1164:topological Radon theorem
849:Topological Radon theorem
190: + 2 points in
73:For example, in the case
2421:10.1112/jlms/s1-41.1.123
1772:Radon theorem for graphs
1306:{\displaystyle f\circ g}
2311:10.2140/pjm.1971.38.471
2072:Kay & Womble (1971)
1718: + 1 remain.
1821:Clarkson et al. (1996)
1707:Carathéodory's theorem
1688:
1634:) and is now known as
1508:
1457:
1411:
1365:
1307:
1194:
1082:
1019:be their images under
1013:
948:
877:
828:
808:
788:
764:
741:
637:
500:
480:
457:
437:
417:
385:
331:
307:
250:
180:
90:Proof and construction
70:
55:
2374:Mathematische Annalen
2137:Archiv der Mathematik
2027:10.1093/imaman/dpl007
1689:
1509:
1458:
1412:
1366:
1308:
1172:
1083:
1014:
949:
855:
829:
809:
789:
765:
742:
638:
501:
481:
458:
438:
418:
386:
332:
281:
224:
181:
69:negative multipliers.
67:
37:
35:in 1921, states that:
2194:; Sturtivant, Carl;
2184:Clarkson, Kenneth L.
1694:points in Euclidean
1642:
1575:randomized algorithm
1483:
1432:
1386:
1340:
1291:
1027:
958:
893:
843:Gaussian elimination
818:
798:
778:
754:
653:
513:
490:
470:
466:The convex hulls of
447:
427:
395:
369:
221:
98:
49:into two sets whose
1503:
1452:
1406:
1360:
1285:Borsuk–Ulam theorem
1238:Borsuk–Ulam theorem
1196:More generally, if
1176:continuous function
2387:10.1007/BF01464231
2247:, pp. 101–179
2150:10.1007/BF01197978
2119:10.1007/BF01896131
1856:10.1007/BF01896131
1774:. In an arbitrary
1684:
1636:Tverberg's theorem
1628:Helge Tverberg
1626:sets was given by
1620:Tverberg's theorem
1504:
1486:
1453:
1435:
1407:
1389:
1361:
1343:
1303:
1078:
1009:
944:
824:
804:
784:
772:convex combination
760:
737:
723:
684:
633:
597:
544:
496:
476:
453:
433:
413:
381:
340:because there are
327:
176:
71:
2345:978-0-387-95373-1
2099:BajmĂłczy, E. G.;
1962:GĂĽnter M. Ziegler
1951:978-3-540-00362-5
1726:convex geometries
1722:Convex geometries
1683:
1614:robust statistics
1610:facility location
827:{\displaystyle p}
807:{\displaystyle J}
787:{\displaystyle I}
774:of the points in
763:{\displaystyle p}
701:
662:
618:
575:
560:
522:
499:{\displaystyle J}
479:{\displaystyle I}
456:{\displaystyle J}
436:{\displaystyle I}
355:, ...,
201:, ...,
94:Consider any set
2460:
2423:
2397:
2381:(1–2): 113–115,
2363:
2348:
2322:
2313:
2285:
2271:
2270:
2248:
2226:
2174:
2160:
2129:
2113:(3–4): 347–350,
2087:
2081:
2075:
2069:
2063:
2057:
2051:
2045:
2039:
2037:
2012:
2000:
1994:
1992:
1973:
1967:
1965:
1931:
1925:
1924:
1906:
1897:(5): 1275–1285.
1882:
1876:
1875:
1835:
1824:
1818:
1776:undirected graph
1768: + 1.
1760: <
1693:
1691:
1690:
1685:
1681:
1606:geometric median
1598:Geometric median
1593:Related concepts
1570: + 1.
1538:geometric median
1513:
1511:
1510:
1505:
1502:
1494:
1462:
1460:
1459:
1454:
1451:
1443:
1416:
1414:
1413:
1408:
1405:
1397:
1370:
1368:
1367:
1362:
1359:
1351:
1312:
1310:
1309:
1304:
1287:to the function
1087:
1085:
1084:
1079:
1077:
1076:
1052:
1051:
1039:
1038:
1018:
1016:
1015:
1010:
1008:
1007:
983:
982:
970:
969:
953:
951:
950:
945:
943:
942:
918:
917:
905:
904:
833:
831:
830:
825:
813:
811:
810:
805:
793:
791:
790:
785:
769:
767:
766:
761:
746:
744:
743:
738:
733:
732:
722:
715:
714:
694:
693:
683:
676:
675:
642:
640:
639:
634:
629:
628:
619:
614:
613:
612:
599:
596:
589:
588:
571:
570:
561:
556:
555:
546:
543:
536:
535:
505:
503:
502:
497:
485:
483:
482:
477:
462:
460:
459:
454:
442:
440:
439:
434:
422:
420:
419:
414:
390:
388:
387:
382:
336:
334:
333:
328:
317:
316:
306:
295:
270:
269:
260:
259:
249:
238:
185:
183:
182:
177:
175:
174:
169:
157:
156:
132:
131:
119:
118:
2468:
2467:
2463:
2462:
2461:
2459:
2458:
2457:
2428:
2427:
2401:
2367:
2352:
2346:
2326:
2289:
2279:
2252:
2230:
2196:Teng, Shang-Hua
2192:Miller, Gary L.
2188:Eppstein, David
2182:
2164:
2133:
2098:
2095:
2090:
2082:
2078:
2070:
2066:
2058:
2054:
2048:Matoušek (2002)
2046:
2042:
2010:
2004:Plastria, Frank
2002:
2001:
1997:
1990:
1975:
1974:
1970:
1952:
1933:
1932:
1928:
1884:
1883:
1879:
1837:
1836:
1827:
1819:
1812:
1808:
1640:
1639:
1595:
1545:Helly's theorem
1534:
1515:is larger than
1481:
1480:
1477:
1430:
1429:
1425:
1420:Therefore, the
1384:
1383:
1338:
1337:
1289:
1288:
1264:on the sphere,
1246:
1157:
1152:
1146:
1141:
1135:
1130:
1124:
1119:
1109:
1104:
1098:
1093:
1062:
1043:
1030:
1025:
1024:
993:
974:
961:
956:
955:
928:
909:
896:
891:
890:
881:affine function
859:affine function
851:
816:
815:
796:
795:
776:
775:
752:
751:
724:
706:
685:
667:
651:
650:
620:
604:
600:
580:
562:
547:
527:
511:
510:
488:
487:
468:
467:
445:
444:
425:
424:
393:
392:
367:
366:
364:
354:
308:
261:
251:
219:
218:
210:
200:
164:
142:
123:
110:
96:
95:
92:
79:Euclidean plane
31:, published by
25:Radon's theorem
17:
12:
11:
5:
2466:
2464:
2456:
2455:
2450:
2445:
2440:
2430:
2429:
2426:
2425:
2399:
2365:
2350:
2344:
2324:
2304:(2): 471–485,
2287:
2277:
2272:. As cited by
2261:(3): 307–316,
2250:
2228:
2210:(3): 357–377,
2180:
2175:. As cited by
2169:(in Russian),
2162:
2131:
2094:
2091:
2089:
2088:
2076:
2064:
2052:
2040:
2021:(4): 387–396,
1995:
1988:
1968:
1958:Anders Björner
1950:
1935:Matoušek, JiĹ™Ă
1926:
1877:
1850:(3): 347–350.
1825:
1809:
1807:
1804:
1792:shortest paths
1744:such that any
1680:
1677:
1674:
1671:
1668:
1665:
1662:
1659:
1656:
1653:
1650:
1647:
1594:
1591:
1533:
1530:
1529:
1528:
1501:
1498:
1493:
1489:
1475:
1468:
1450:
1447:
1442:
1438:
1423:
1418:
1404:
1401:
1396:
1392:
1380:
1358:
1355:
1350:
1346:
1326:
1325:
1318:
1302:
1299:
1296:
1281:
1245:
1242:
1155:
1150:
1144:
1139:
1133:
1128:
1122:
1117:
1107:
1102:
1096:
1091:
1075:
1072:
1069:
1065:
1061:
1058:
1055:
1050:
1046:
1042:
1037:
1033:
1006:
1003:
1000:
996:
992:
989:
986:
981:
977:
973:
968:
964:
941:
938:
935:
931:
927:
924:
921:
916:
912:
908:
903:
899:
850:
847:
823:
803:
783:
759:
748:
747:
736:
731:
727:
721:
718:
713:
709:
704:
700:
697:
692:
688:
682:
679:
674:
670:
665:
661:
658:
644:
643:
632:
627:
623:
617:
611:
607:
603:
595:
592:
587:
583:
578:
574:
569:
565:
559:
554:
550:
542:
539:
534:
530:
525:
521:
518:
495:
475:
452:
432:
412:
409:
406:
403:
400:
380:
377:
374:
363: + 2
359:
352:
338:
337:
326:
323:
320:
315:
311:
305:
302:
299:
294:
291:
288:
284:
279:
276:
273:
268:
264:
258:
254:
248:
245:
242:
237:
234:
231:
227:
209: + 2
205:
198:
173:
168:
163:
160:
155:
152:
149:
145:
141:
138:
135:
130:
126:
122:
117:
113:
109:
106:
103:
91:
88:
15:
13:
10:
9:
6:
4:
3:
2:
2465:
2454:
2451:
2449:
2446:
2444:
2441:
2439:
2436:
2435:
2433:
2422:
2418:
2414:
2410:
2409:
2404:
2400:
2396:
2392:
2388:
2384:
2380:
2376:
2375:
2370:
2366:
2361:
2360:
2355:
2351:
2347:
2341:
2337:
2333:
2329:
2325:
2321:
2317:
2312:
2307:
2303:
2299:
2298:
2293:
2288:
2283:
2278:
2275:
2269:
2264:
2260:
2256:
2251:
2246:
2242:
2238:
2234:
2229:
2225:
2221:
2217:
2213:
2209:
2205:
2201:
2197:
2193:
2189:
2185:
2181:
2178:
2172:
2168:
2163:
2159:
2155:
2151:
2147:
2143:
2139:
2138:
2132:
2128:
2124:
2120:
2116:
2112:
2108:
2107:
2102:
2097:
2096:
2092:
2085:
2084:Duchet (1987)
2080:
2077:
2073:
2068:
2065:
2061:
2056:
2053:
2049:
2044:
2041:
2036:
2032:
2028:
2024:
2020:
2016:
2009:
2005:
1999:
1996:
1991:
1989:9780387235394
1985:
1981:
1980:
1972:
1969:
1966:, Section 4.3
1964:
1963:
1959:
1953:
1947:
1943:
1941:
1936:
1930:
1927:
1922:
1918:
1914:
1910:
1905:
1900:
1896:
1892:
1888:
1881:
1878:
1873:
1869:
1865:
1861:
1857:
1853:
1849:
1845:
1841:
1834:
1832:
1830:
1826:
1822:
1817:
1815:
1811:
1805:
1803:
1801:
1797:
1796:Chepoi (1986)
1793:
1789:
1788:clique number
1784:
1781:
1777:
1773:
1769:
1767:
1764: ≤
1763:
1759:
1755:
1751:
1747:
1743:
1739:
1735:
1731:
1727:
1723:
1719:
1717:
1713:
1709:
1708:
1703:
1701:
1697:
1678:
1675:
1669:
1666:
1663:
1654:
1651:
1648:
1637:
1633:
1629:
1625:
1621:
1617:
1615:
1611:
1607:
1603:
1599:
1592:
1590:
1588:
1584:
1583:approximation
1580:
1576:
1571:
1569:
1565:
1561:
1557:
1553:
1548:
1546:
1541:
1539:
1531:
1526:
1522:
1518:
1514:
1499:
1496:
1487:
1473:
1469:
1466:
1448:
1445:
1436:
1427:
1419:
1402:
1399:
1390:
1381:
1378:
1374:
1356:
1353:
1344:
1335:
1331:
1330:
1329:
1323:
1319:
1316:
1300:
1297:
1294:
1286:
1282:
1279:
1275:
1271:
1267:
1263:
1259:
1255:
1251:
1250:
1249:
1243:
1241:
1239:
1235:
1231:
1227:
1223:
1219:
1215:
1211:
1207:
1203:
1199:
1193:
1191:
1190:
1185:
1181:
1177:
1171:
1169:
1165:
1161:
1153:
1142:
1131:
1120:
1113:
1105:
1094:
1073:
1070:
1067:
1063:
1059:
1056:
1053:
1048:
1044:
1040:
1035:
1031:
1022:
1004:
1001:
998:
994:
990:
987:
984:
979:
975:
971:
966:
962:
939:
936:
933:
929:
925:
922:
919:
914:
910:
906:
901:
897:
888:
887:
882:
876:
874:
873:
868:
864:
860:
854:
848:
846:
844:
840:
835:
821:
814:. Therefore,
801:
781:
773:
757:
734:
729:
725:
719:
716:
711:
707:
702:
698:
695:
690:
686:
680:
677:
672:
668:
663:
659:
656:
649:
648:
647:
630:
625:
621:
615:
609:
605:
601:
593:
590:
585:
581:
576:
572:
567:
563:
557:
552:
548:
540:
537:
532:
528:
523:
519:
516:
509:
508:
507:
493:
473:
464:
450:
430:
410:
404:
401:
398:
378:
375:
372:
362:
358:
351:
347:
343:
324:
321:
318:
313:
309:
303:
300:
297:
292:
289:
286:
282:
277:
274:
271:
266:
262:
256:
252:
246:
243:
240:
235:
232:
229:
225:
217:
216:
215:
214:
208:
204:
197:
193:
189:
171:
161:
153:
150:
147:
143:
139:
136:
133:
128:
124:
120:
115:
111:
104:
101:
89:
87:
85:
84:line segments
80:
76:
66:
62:
60:
54:
52:
48:
44:
43:
36:
34:
30:
26:
22:
2448:Convex hulls
2412:
2406:
2403:Tverberg, H.
2378:
2372:
2358:
2354:Matoušek, J.
2331:
2328:Matoušek, J.
2301:
2295:
2281:
2258:
2254:
2240:
2233:GrĂĽnbaum, B.
2231:Danzer, L.;
2207:
2203:
2170:
2167:Mat. Issled.
2166:
2144:(1): 95–98,
2141:
2135:
2110:
2104:
2079:
2067:
2055:
2043:
2018:
2014:
1998:
1978:
1971:
1955:
1938:
1929:
1894:
1890:
1880:
1847:
1843:
1771:
1770:
1765:
1761:
1757:
1753:
1749:
1745:
1741:
1737:
1733:
1721:
1720:
1715:
1711:
1706:
1704:
1699:
1695:
1623:
1619:
1618:
1597:
1596:
1578:
1572:
1567:
1563:
1559:
1555:
1552:VC dimension
1549:
1542:
1535:
1532:Applications
1524:
1520:
1516:
1479:
1471:
1464:
1379:with itself.
1376:
1373:deleted join
1333:
1327:
1321:
1314:
1277:
1273:
1269:
1265:
1261:
1253:
1247:
1229:
1225:
1221:
1217:
1213:
1209:
1205:
1201:
1197:
1195:
1187:
1179:
1174:If Ć’ is any
1173:
1167:
1163:
1159:
1148:
1137:
1126:
1115:
1111:
1100:
1089:
1020:
884:
878:
870:
862:
857:If Ć’ is any
856:
852:
836:
749:
645:
465:
360:
356:
349:
345:
341:
339:
206:
202:
195:
191:
187:
93:
74:
72:
58:
56:
51:convex hulls
40:
38:
33:Johann Radon
24:
18:
2415:: 123–128,
1587:centerpoint
1234:hypersphere
61:of the set.
59:Radon point
53:intersect.
47:partitioned
29:convex sets
2432:Categories
2101:Bárány, I.
2093:References
2035:1126.90046
1527:intersect.
1478:-index of
1474:, if the Z
1283:Apply the
883:from Δ to
839:polynomial
2395:121627696
2369:Radon, J.
2241:Convexity
2173:: 164–177
2158:120983560
1913:0002-9939
1864:1588-2632
1730:empty set
1667:−
1497:∗
1492:Δ
1446:∗
1441:Δ
1400:∗
1395:Δ
1354:∗
1349:Δ
1298:∘
1057:…
988:…
923:…
717:∈
703:∑
699:−
678:∈
664:∑
602:−
591:∈
577:∑
538:∈
524:∑
408:∖
376:⊆
283:∑
226:∑
162:⊂
137:…
2237:Klee, V.
2198:(1996),
2127:12971298
2050:, p. 11.
2006:(2006),
1937:(2007).
1872:12971298
1200:is any (
1178:from a (
861:from a (
21:geometry
2320:0310766
2224:1409651
1921:7790459
1780:induced
1630: (
1463:equals
1371:be the
1184:simplex
1108:j in J,
867:simplex
45:can be
2393:
2342:
2318:
2222:
2156:
2125:
2033:
1986:
1948:
1919:
1911:
1870:
1862:
1682:
1604:. The
1602:median
1426:-index
1272:) and
1258:sphere
1244:Proofs
1134:i in I
1123:i in I
1097:i in I
889:. Let
646:where
365:. Let
2391:S2CID
2154:S2CID
2123:S2CID
2011:(PDF)
1917:S2CID
1868:S2CID
1806:Notes
1585:to a
1186:Δ to
1099:and (
869:Δ to
2340:ISBN
1984:ISBN
1960:and
1946:ISBN
1909:ISSN
1860:ISSN
1798:and
1783:path
1632:1966
1612:and
1332:Let
1156:in j
1145:in J
486:and
443:and
2417:doi
2383:doi
2306:doi
2263:doi
2212:doi
2146:doi
2115:doi
2031:Zbl
2023:doi
1899:doi
1895:126
1852:doi
1554:of
1467:+1.
1428:of
1375:of
1208:to
1154:)j
1143:)j
186:of
27:on
19:In
2434::
2413:41
2411:,
2389:,
2379:83
2377:,
2334:,
2316:MR
2314:,
2302:38
2300:,
2294:,
2259:44
2257:,
2235:;
2220:MR
2218:,
2206:,
2202:,
2190:;
2186:;
2171:87
2152:,
2142:52
2140:,
2121:,
2111:34
2109:,
2029:,
2019:17
2017:,
2013:,
1954:.
1915:.
1907:.
1893:.
1889:.
1866:.
1858:.
1848:34
1846:.
1842:.
1828:^
1813:^
1802:.
1766:ch
1573:A
1276:(-
86:.
23:,
2424:.
2419::
2398:.
2385::
2364:.
2349:.
2323:.
2308::
2286:.
2276:.
2265::
2249:.
2227:.
2214::
2208:6
2179:.
2161:.
2148::
2130:.
2117::
2086:.
2074:.
2038:.
2025::
1993:.
1923:.
1901::
1874:.
1854::
1823:.
1762:r
1758:h
1754:c
1750:h
1746:r
1742:r
1738:S
1734:S
1716:d
1712:d
1700:r
1696:d
1679:1
1676:+
1673:)
1670:1
1664:r
1661:(
1658:)
1655:1
1652:+
1649:d
1646:(
1624:r
1579:d
1568:d
1564:d
1560:d
1556:d
1525:K
1521:K
1517:d
1500:2
1488:K
1476:2
1472:K
1465:d
1449:2
1437:K
1424:2
1422:Z
1403:2
1391:K
1377:K
1357:2
1345:K
1334:K
1322:f
1315:y
1301:g
1295:f
1278:x
1274:g
1270:x
1268:(
1266:g
1262:x
1254:g
1230:g
1226:K
1222:g
1218:g
1214:g
1210:d
1206:K
1202:d
1198:K
1189:R
1180:d
1168:f
1160:f
1151:j
1149:v
1140:j
1138:x
1132:)
1129:i
1127:v
1121:)
1118:i
1116:x
1112:f
1106:)
1103:j
1101:x
1095:)
1092:i
1090:x
1074:2
1071:+
1068:d
1064:x
1060:,
1054:,
1049:2
1045:x
1041:,
1036:1
1032:x
1021:Ć’
1005:2
1002:+
999:d
995:x
991:,
985:,
980:2
976:x
972:,
967:1
963:x
940:2
937:+
934:d
930:v
926:,
920:,
915:2
911:v
907:,
902:1
898:v
886:R
872:R
863:d
822:p
802:J
782:I
758:p
735:.
730:j
726:a
720:J
712:j
708:x
696:=
691:i
687:a
681:I
673:i
669:x
660:=
657:A
631:,
626:j
622:x
616:A
610:j
606:a
594:J
586:j
582:x
573:=
568:i
564:x
558:A
553:i
549:a
541:I
533:i
529:x
520:=
517:p
494:J
474:I
451:J
431:I
411:I
405:X
402:=
399:J
379:X
373:I
361:d
357:a
353:1
350:a
346:d
342:d
325:,
322:0
319:=
314:i
310:a
304:2
301:+
298:d
293:1
290:=
287:i
278:,
275:0
272:=
267:i
263:x
257:i
253:a
247:2
244:+
241:d
236:1
233:=
230:i
207:d
203:a
199:1
196:a
192:d
188:d
172:d
167:R
159:}
154:2
151:+
148:d
144:x
140:,
134:,
129:2
125:x
121:,
116:1
112:x
108:{
105:=
102:X
75:d
42:R
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
