1149:, used earlier in some heuristics. It starts with a large sphere that covers all points and gradually shrinks it until it cannot be shrunk further. The algorithm features correct termination rules in cases of degeneracies, overlooked by prior authors; and efficient handling of partial solutions, which produces a major speed-up. The authors verified that the algorithm is efficient in practice in low and moderately low (up to 10,000) dimensions and claim it does not exhibit numerical stability problems in its floating-point operations. A C++ implementation of the algorithm is available as an open-source project.
38:
143:, that is, the sphere with minimal radius among all bounding spheres. It may be proven that such a sphere is unique: If there are two of them, then the objects in question lie within their intersection. But an intersection of two non-coinciding spheres of equal radius is contained in a sphere of smaller radius.
186:
or natural (usually thermal) processes, in which case the cluster represents a perturbation of an ideal point. In some circumstances this ideal point may be used as a substitute for the points in the cluster, advantageous in reducing calculation time.
1130:
1140:
Fischer et al. (2003) proposed an exact solver, though the algorithm does not have a polynomial running time in the worst case. The algorithm is purely combinatorial and implements a pivoting scheme similar to the
478:
In 1990, Jack Ritter proposed a simple algorithm to find a non-minimal bounding sphere. It is widely used in various applications for its simplicity. The algorithm works in this way:
1052:
expansion of the solution on the subset is a bounding sphere of the whole set. The coreset is constructed incrementally by adding the farthest point into the set in each iteration.
1160:
proposed the "extremal points optimal sphere" method with controllable speed to accuracy approximation to solve the bounding sphere problem. This method works by taking a set of
997:
198:
problems in a reasonable time. The point chosen is not usually the center of the sphere, as this can be biased by outliers, but instead some form of average location such as a
298:
379:
1050:
962:
936:
1058:
1293:
862:
461:
408:
1241:
1261:
1218:
1198:
1178:
1017:
902:
882:
826:
806:
786:
766:
743:
723:
703:
683:
663:
643:
623:
603:
580:
560:
540:
520:
500:
428:
243:
107:
71:
128:. There are several fast and simple bounding sphere construction algorithms with a high practical value in real-time computer graphics applications.
1605:; Yıldırım, E. Alper (2003), "Computing core-sets and approximate smallest enclosing hyperspheres in high dimensions", in Ladner, Richard E. (ed.),
1243:
extremal points of these projections. The algorithm then iterates over the remaining points, if any, growing the sphere if necessary. For large
904:-dimensional space, which makes it very efficient. However, it gives only a coarse result which is usually 5% to 20% larger than the optimum.
430:. The paper provides experimental results demonstrating its practicality in higher dimensions. A more recent deterministic algorithm of
225:" algorithm which finds the optimum bounding sphere and runs in linear time if the dimension is fixed as a constant. When the dimension
467:
194:
the clustering of values to an ideal point may also be used to reduce the number of inputs in order to obtain approximate values for
17:
1652:
1498:
1681:
1263:
this method is orders of magnitude faster than exact methods, while giving comparable results. It has a worst case time of
221:
studied the 1-center problem extensively and published on it at least five times in the 1980s. In 1983, he proposed a "
1523:
1476:
1547:
1607:
Proceedings of the Fifth
Workshop on Algorithm Engineering and Experiments, Baltimore, MD, USA, January 11, 2003
1342:
SIGRAD 2008: The Annual SIGRAD Conference, Special Theme: Interaction, November 27-28, 2008, Stockholm, Sweden
1697:
146:
The problem of computing the center of a minimal bounding sphere is also known as the "unweighted
Euclidean
1633:
Algorithms: ESA 2003, 11th Annual
European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings
967:
248:
322:
1624:
1344:, Linköping Electronic Conference Proceedings, vol. 34, Linköping, Sweden: Linköping University
1029:
941:
915:
1684:– describes several algorithms for enclosing a point set, including Megiddo's linear-time algorithm
1631:
42:
1563:
1125:{\displaystyle O({\frac {nd}{\epsilon }}+{\frac {1}{\epsilon ^{4.5}}}\log {\frac {1}{\epsilon }})}
1463:, Lecture Notes in Computer Science, vol. 555, Berlin, Germany: Springer, pp. 359–370,
175:
1337:
1558:
121:
1458:
1602:
1460:
New
Results and New Trends in Computer Science: Graz, Austria, June 20–21, 1991, Proceedings
1580:
1486:
1313:
1309:
1266:
835:
308:
171:
437:
384:
8:
1639:, Lecture Notes in Computer Science, vol. 2832, Springer, Berlin, pp. 630–641,
191:
136:
1223:
1584:
1436:
1395:
1246:
1203:
1183:
1163:
1146:
1002:
887:
867:
811:
791:
771:
751:
728:
708:
688:
668:
648:
628:
608:
588:
565:
545:
525:
505:
485:
413:
312:
228:
92:
56:
1419:(2018). "Improved deterministic algorithms for linear programming in low dimensions".
1648:
1519:
1472:
1457:(1991), "Smallest enclosing disks (balls and ellipsoids)", in Maurer, Hermann (ed.),
183:
117:
1399:
210:
There are exact and approximate algorithms for the solving bounding sphere problem.
1702:
1640:
1588:
1568:
1539:
1514:
Ritter, Jack (1990), "An efficient bounding sphere", in
Glassner, Andrew S. (ed.),
1464:
1440:
1428:
1385:
222:
164:
147:
1644:
1576:
1482:
1304:
1220:
serves as a speed-accuracy trade-off variable. An exact solver is applied to the
125:
31:
139:, the objects are typically points, and generally the sphere of interest is the
1369:
1355:
1142:
316:
218:
1691:
199:
1555:
Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of
Computing
1416:
1055:
Kumar et al. improved this approximation algorithm so that it runs in time
431:
110:
1572:
1518:, San Diego, CA, US: Academic Press Professional, Inc., pp. 301–303,
463:
time, with a smaller (but still exponential) dependence on the dimension.
37:
1543:
179:
50:
1390:
1373:
1468:
808:
be a point outside the ball, constructs a new ball covering both point
132:
1454:
304:
1432:
964:
approximation means that the constructed sphere has radius at most
1666:
1023:
828:
and previous ball. Repeat this step until all points are covered.
195:
1180:
direction vectors and projecting all points onto each vector in
1374:"Linear programming in linear time when the dimension is fixed"
167:, where groups of similar data points are classified together.
1625:"Fast smallest-enclosing-ball computation in high dimensions"
74:
300:, which is impractical for high-dimensional applications.
53:, given a non-empty set of objects of finite extension in
470:(CGAL) contains an implementation of Welzl's algorithm.
245:
is taken into account, the execution time complexity is
1623:
Fischer, Kaspar; Gärtner, Bernd; Kutz, Martin (2003),
1019:
is the smallest possible radius of a bounding sphere.
938:
approximation to the bounding sphere problem, where a
1600:
1499:
CGAL 4.3 - Bounding
Volumes - Min_sphere_of_spheres_d
1269:
1249:
1226:
1206:
1186:
1166:
1061:
1032:
1005:
970:
944:
918:
890:
870:
838:
814:
794:
774:
754:
731:
711:
691:
671:
651:
631:
611:
591:
568:
548:
528:
508:
488:
440:
416:
387:
325:
319:. The expected running time of Welzl's algorithm is
251:
231:
95:
59:
1537:
1622:
1287:
1255:
1235:
1212:
1192:
1172:
1124:
1044:
1011:
991:
956:
930:
896:
876:
856:
820:
800:
780:
760:
737:
717:
697:
677:
657:
637:
617:
597:
574:
554:
534:
514:
494:
455:
422:
402:
373:
292:
237:
101:
65:
45:, the case of the bounding sphere in 2 dimensions.
1152:
1689:
788:, then we get a bounding sphere. Otherwise, let
1630:, in Battista, Giuseppe Di; Zwick, Uri (eds.),
907:
1618:
1616:
705:, the radius as half of the distance between
1609:, Philadelphia, PA, US: SIAM, pp. 45–55
1509:
1507:
202:point is computed to represent the cluster.
1613:
1557:, New York, NY, US: ACM, pp. 250–257,
473:
1356:"Nimrod Megiddo's resume and publications"
1562:
1531:
1504:
1389:
1338:"Fast and tight fitting bounding spheres"
1135:
468:Computational Geometry Algorithms Library
124:, a bounding sphere is a special type of
1594:
1411:
1409:
36:
1368:
1335:
1157:
14:
1690:
1548:"Approximate clustering via core-sets"
1513:
1447:
1331:
1329:
625:, which has the largest distance from
562:, which has the largest distance from
1453:
1406:
665:, with its centre as the midpoint of
213:
182:within a sphere may be attributed to
27:Sphere that contains a set of objects
1415:
1362:
1326:
24:
25:
1714:
1682:Smallest Enclosing Circle Problem
1675:
992:{\displaystyle (1+\varepsilon )r}
113:containing all of these objects.
77:, for example a set of points, a
832:Ritter's algorithm runs in time
293:{\displaystyle O(2^{O(d^{2})}n)}
1660:
374:{\displaystyle O((d+1)(d+1)!n)}
153:
1492:
1421:ACM Transactions on Algorithms
1348:
1282:
1273:
1153:Extremal points optimal sphere
1119:
1065:
1045:{\displaystyle 1+\varepsilon }
983:
971:
957:{\displaystyle 1+\varepsilon }
931:{\displaystyle 1+\varepsilon }
851:
842:
450:
444:
397:
391:
368:
359:
347:
344:
332:
329:
287:
279:
266:
255:
13:
1:
1319:
205:
158:
1667:miniball open-source project
1645:10.1007/978-3-540-39658-1_57
908:Core-set based approximation
311:, generalizing a randomized
30:For the planar problem, see
7:
1427:(3): Article 30, 10 pages.
1298:
163:Such spheres are useful in
10:
1719:
1026:is a small subset, that a
912:Bădoiu et al. presented a
29:
645:. Set up an initial ball
381:, which again reduces to
1336:Larsson, Thomas (2008),
864:on inputs consisting of
474:Ritter's bounding sphere
410:for any fixed dimension
307:proposed a much simpler
43:smallest bounding circle
18:Minimal enclosing sphere
1501:, retrieved 2014-03-30.
141:minimal bounding sphere
1603:Mitchell, Joseph S. B.
1289:
1257:
1237:
1214:
1194:
1174:
1136:Fischer's exact solver
1126:
1046:
1013:
993:
958:
932:
898:
878:
858:
822:
802:
782:
762:
739:
719:
699:
679:
659:
639:
619:
599:
576:
556:
536:
516:
496:
457:
424:
404:
375:
294:
239:
122:computational geometry
103:
67:
46:
41:Some instances of the
1573:10.1145/509907.509947
1290:
1288:{\displaystyle O(sn)}
1258:
1238:
1215:
1195:
1175:
1127:
1047:
1014:
994:
959:
933:
899:
879:
859:
857:{\displaystyle O(nd)}
823:
803:
783:
763:
740:
720:
700:
680:
660:
640:
620:
600:
577:
557:
537:
517:
497:
458:
425:
405:
376:
295:
240:
104:
68:
40:
1698:Geometric algorithms
1314:circumscribed circle
1310:Circumscribed sphere
1267:
1247:
1224:
1204:
1184:
1164:
1059:
1030:
1003:
968:
942:
916:
888:
868:
836:
812:
792:
772:
752:
729:
709:
689:
669:
649:
629:
609:
589:
566:
546:
526:
506:
486:
456:{\displaystyle O(n)}
438:
414:
403:{\displaystyle O(n)}
385:
323:
309:randomized algorithm
249:
229:
172:statistical analysis
93:
57:
1391:10.1145/2422.322418
192:operations research
137:operations research
1469:10.1007/BFb0038202
1378:Journal of the ACM
1285:
1253:
1236:{\displaystyle 2s}
1233:
1210:
1190:
1170:
1147:linear programming
1122:
1042:
1009:
989:
954:
928:
894:
874:
854:
818:
798:
778:
758:
735:
715:
695:
675:
655:
635:
615:
595:
572:
552:
532:
512:
492:
453:
420:
400:
371:
313:linear programming
290:
235:
214:Linear programming
99:
89:for that set is a
63:
47:
1654:978-3-540-20064-2
1540:Har-Peled, Sariel
1256:{\displaystyle n}
1213:{\displaystyle s}
1193:{\displaystyle s}
1173:{\displaystyle s}
1117:
1101:
1081:
1012:{\displaystyle r}
897:{\displaystyle d}
877:{\displaystyle n}
821:{\displaystyle p}
801:{\displaystyle p}
781:{\displaystyle B}
761:{\displaystyle P}
748:If all points in
738:{\displaystyle z}
718:{\displaystyle y}
698:{\displaystyle z}
678:{\displaystyle y}
658:{\displaystyle B}
638:{\displaystyle y}
618:{\displaystyle P}
598:{\displaystyle z}
575:{\displaystyle x}
555:{\displaystyle P}
535:{\displaystyle y}
522:, search a point
515:{\displaystyle P}
495:{\displaystyle x}
423:{\displaystyle d}
238:{\displaystyle d}
184:measurement error
118:computer graphics
102:{\displaystyle d}
66:{\displaystyle d}
16:(Redirected from
1710:
1669:
1664:
1658:
1657:
1638:
1629:
1620:
1611:
1610:
1598:
1592:
1591:
1566:
1552:
1535:
1529:
1528:
1511:
1502:
1496:
1490:
1489:
1451:
1445:
1444:
1413:
1404:
1403:
1393:
1366:
1360:
1359:
1352:
1346:
1345:
1333:
1294:
1292:
1291:
1286:
1262:
1260:
1259:
1254:
1242:
1240:
1239:
1234:
1219:
1217:
1216:
1211:
1199:
1197:
1196:
1191:
1179:
1177:
1176:
1171:
1131:
1129:
1128:
1123:
1118:
1110:
1102:
1100:
1099:
1087:
1082:
1077:
1069:
1051:
1049:
1048:
1043:
1018:
1016:
1015:
1010:
998:
996:
995:
990:
963:
961:
960:
955:
937:
935:
934:
929:
903:
901:
900:
895:
883:
881:
880:
875:
863:
861:
860:
855:
827:
825:
824:
819:
807:
805:
804:
799:
787:
785:
784:
779:
768:are within ball
767:
765:
764:
759:
744:
742:
741:
736:
724:
722:
721:
716:
704:
702:
701:
696:
684:
682:
681:
676:
664:
662:
661:
656:
644:
642:
641:
636:
624:
622:
621:
616:
604:
602:
601:
596:
581:
579:
578:
573:
561:
559:
558:
553:
541:
539:
538:
533:
521:
519:
518:
513:
501:
499:
498:
493:
466:The open-source
462:
460:
459:
454:
429:
427:
426:
421:
409:
407:
406:
401:
380:
378:
377:
372:
299:
297:
296:
291:
283:
282:
278:
277:
244:
242:
241:
236:
223:prune and search
148:1-center problem
108:
106:
105:
100:
83:enclosing sphere
72:
70:
69:
64:
21:
1718:
1717:
1713:
1712:
1711:
1709:
1708:
1707:
1688:
1687:
1678:
1673:
1672:
1665:
1661:
1655:
1636:
1627:
1621:
1614:
1601:Kumar, Piyush;
1599:
1595:
1550:
1538:Bādoiu, Mihai;
1536:
1532:
1526:
1512:
1505:
1497:
1493:
1479:
1452:
1448:
1433:10.1145/3155312
1414:
1407:
1370:Megiddo, Nimrod
1367:
1363:
1354:
1353:
1349:
1334:
1327:
1322:
1305:Bounding volume
1301:
1268:
1265:
1264:
1248:
1245:
1244:
1225:
1222:
1221:
1205:
1202:
1201:
1185:
1182:
1181:
1165:
1162:
1161:
1155:
1138:
1109:
1095:
1091:
1086:
1070:
1068:
1060:
1057:
1056:
1031:
1028:
1027:
1004:
1001:
1000:
969:
966:
965:
943:
940:
939:
917:
914:
913:
910:
889:
886:
885:
869:
866:
865:
837:
834:
833:
813:
810:
809:
793:
790:
789:
773:
770:
769:
753:
750:
749:
730:
727:
726:
710:
707:
706:
690:
687:
686:
670:
667:
666:
650:
647:
646:
630:
627:
626:
610:
607:
606:
590:
587:
586:
585:Search a point
567:
564:
563:
547:
544:
543:
527:
524:
523:
507:
504:
503:
487:
484:
483:
476:
439:
436:
435:
415:
412:
411:
386:
383:
382:
324:
321:
320:
273:
269:
262:
258:
250:
247:
246:
230:
227:
226:
216:
208:
161:
156:
126:bounding volume
94:
91:
90:
79:bounding sphere
58:
55:
54:
35:
32:Bounding circle
28:
23:
22:
15:
12:
11:
5:
1716:
1706:
1705:
1700:
1686:
1685:
1677:
1676:External links
1674:
1671:
1670:
1659:
1653:
1612:
1593:
1530:
1524:
1503:
1491:
1477:
1446:
1405:
1384:(1): 114–147.
1361:
1347:
1324:
1323:
1321:
1318:
1317:
1316:
1307:
1300:
1297:
1284:
1281:
1278:
1275:
1272:
1252:
1232:
1229:
1209:
1189:
1169:
1158:Larsson (2008)
1154:
1151:
1143:simplex method
1137:
1134:
1121:
1116:
1113:
1108:
1105:
1098:
1094:
1090:
1085:
1080:
1076:
1073:
1067:
1064:
1041:
1038:
1035:
1008:
988:
985:
982:
979:
976:
973:
953:
950:
947:
927:
924:
921:
909:
906:
893:
873:
853:
850:
847:
844:
841:
830:
829:
817:
797:
777:
757:
746:
734:
714:
694:
674:
654:
634:
614:
594:
583:
571:
551:
531:
511:
491:
475:
472:
452:
449:
446:
443:
419:
399:
396:
393:
390:
370:
367:
364:
361:
358:
355:
352:
349:
346:
343:
340:
337:
334:
331:
328:
317:Raimund Seidel
289:
286:
281:
276:
272:
268:
265:
261:
257:
254:
234:
219:Nimrod Megiddo
215:
212:
207:
204:
160:
157:
155:
152:
98:
87:enclosing ball
62:
26:
9:
6:
4:
3:
2:
1715:
1704:
1701:
1699:
1696:
1695:
1693:
1683:
1680:
1679:
1668:
1663:
1656:
1650:
1646:
1642:
1635:
1634:
1626:
1619:
1617:
1608:
1604:
1597:
1590:
1586:
1582:
1578:
1574:
1570:
1565:
1564:10.1.1.4.9395
1560:
1556:
1549:
1545:
1541:
1534:
1527:
1525:0-12-286166-3
1521:
1517:
1516:Graphics Gems
1510:
1508:
1500:
1495:
1488:
1484:
1480:
1478:3-540-54869-6
1474:
1470:
1466:
1462:
1461:
1456:
1450:
1442:
1438:
1434:
1430:
1426:
1422:
1418:
1417:Chan, Timothy
1412:
1410:
1401:
1397:
1392:
1387:
1383:
1379:
1375:
1371:
1365:
1357:
1351:
1343:
1339:
1332:
1330:
1325:
1315:
1311:
1308:
1306:
1303:
1302:
1296:
1279:
1276:
1270:
1250:
1230:
1227:
1207:
1187:
1167:
1159:
1150:
1148:
1144:
1133:
1114:
1111:
1106:
1103:
1096:
1092:
1088:
1083:
1078:
1074:
1071:
1062:
1053:
1039:
1036:
1033:
1025:
1020:
1006:
986:
980:
977:
974:
951:
948:
945:
925:
922:
919:
905:
891:
871:
848:
845:
839:
815:
795:
775:
755:
747:
732:
712:
692:
672:
652:
632:
612:
592:
584:
569:
549:
529:
509:
489:
482:Pick a point
481:
480:
479:
471:
469:
464:
447:
441:
434:also runs in
433:
417:
394:
388:
365:
362:
356:
353:
350:
341:
338:
335:
326:
318:
315:algorithm by
314:
310:
306:
301:
284:
274:
270:
263:
259:
252:
232:
224:
220:
211:
203:
201:
200:least squares
197:
193:
188:
185:
181:
177:
173:
168:
166:
151:
149:
144:
142:
138:
134:
129:
127:
123:
119:
114:
112:
109:-dimensional
96:
88:
84:
80:
76:
73:-dimensional
60:
52:
44:
39:
33:
19:
1662:
1632:
1606:
1596:
1554:
1544:Indyk, Piotr
1533:
1515:
1494:
1459:
1449:
1424:
1420:
1381:
1377:
1364:
1350:
1341:
1156:
1139:
1054:
1021:
911:
831:
477:
465:
432:Timothy Chan
302:
217:
209:
189:
169:
162:
154:Applications
145:
140:
130:
115:
111:solid sphere
86:
82:
78:
48:
180:data points
51:mathematics
1692:Categories
1455:Welzl, Emo
1320:References
884:points in
206:Algorithms
176:scattering
165:clustering
159:Clustering
133:statistics
1559:CiteSeerX
1115:ϵ
1107:
1093:ϵ
1079:ϵ
1040:ε
981:ε
952:ε
926:ε
305:Emo Welzl
303:In 1991,
1546:(2002),
1400:12686747
1372:(1988).
1299:See also
999:, where
116:Used in
1703:Spheres
1589:5409535
1581:2121149
1487:1254721
1441:9345339
1024:coreset
196:NP-hard
1651:
1587:
1579:
1561:
1522:
1485:
1475:
1439:
1398:
1637:(PDF)
1628:(PDF)
1585:S2CID
1551:(PDF)
1437:S2CID
1396:S2CID
502:from
75:space
1649:ISBN
1520:ISBN
1473:ISBN
1145:for
725:and
685:and
174:the
135:and
120:and
1641:doi
1569:doi
1465:doi
1429:doi
1386:doi
1295:.
1104:log
1097:4.5
605:in
542:in
190:In
178:of
170:In
150:".
131:In
85:or
49:In
1694::
1647:,
1615:^
1583:,
1577:MR
1575:,
1567:,
1553:,
1542:;
1506:^
1483:MR
1481:,
1471:,
1435:.
1425:14
1423:.
1408:^
1394:.
1382:33
1380:.
1376:.
1340:,
1328:^
1312:,
1200:;
1132:.
1022:A
81:,
1643::
1571::
1467::
1443:.
1431::
1402:.
1388::
1358:.
1283:)
1280:n
1277:s
1274:(
1271:O
1251:n
1231:s
1228:2
1208:s
1188:s
1168:s
1120:)
1112:1
1089:1
1084:+
1075:d
1072:n
1066:(
1063:O
1037:+
1034:1
1007:r
987:r
984:)
978:+
975:1
972:(
949:+
946:1
923:+
920:1
892:d
872:n
852:)
849:d
846:n
843:(
840:O
816:p
796:p
776:B
756:P
745:;
733:z
713:y
693:z
673:y
653:B
633:y
613:P
593:z
582:;
570:x
550:P
530:y
510:P
490:x
451:)
448:n
445:(
442:O
418:d
398:)
395:n
392:(
389:O
369:)
366:n
363:!
360:)
357:1
354:+
351:d
348:(
345:)
342:1
339:+
336:d
333:(
330:(
327:O
288:)
285:n
280:)
275:2
271:d
267:(
264:O
260:2
256:(
253:O
233:d
97:d
61:d
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
