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