{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T05:12:37Z","timestamp":1790745157003,"version":"4.1.0"},"reference-count":45,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2020,7,22]],"date-time":"2020-07-22T00:00:00Z","timestamp":1595376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We suggest a provable and practical approximation algorithm for fitting a set P of n points in     R d     to a sphere. Here, a sphere is represented by its center     x \u2208  R d      and radius     r  &gt;  0    . The goal is to minimize the sum      \u2211  p \u2208 P   \u2223  p \u2212 x  \u2212 r \u2223     of distances to the points up to a multiplicative factor of     1 \u00b1 \u03b5    , for a given constant     \u03b5 &gt; 0    , over every such r and x. Our main technical result is a data summarization of the input set, called coreset, that approximates the above sum of distances on the original (big) set P for every sphere. Then, an accurate sphere can be extracted quickly via an inefficient exhaustive search from the small coreset. Most articles focus mainly on sphere identification (e.g., circles in     2 D     image) rather than finding the exact match (in the sense of extent measures), and do not provide approximation guarantees. We implement our algorithm and provide extensive experimental results on both synthetic and real-world data. We then combine our algorithm in a mechanical pressure control system whose main bottleneck is tracking a falling ball. Full open source is also provided.<\/jats:p>","DOI":"10.3390\/a13080177","type":"journal-article","created":{"date-parts":[[2020,7,23]],"date-time":"2020-07-23T10:14:06Z","timestamp":1595499246000},"page":"177","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Sphere Fitting with Applications to Machine Tracking"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6408-3373","authenticated-orcid":false,"given":"Dror","family":"Epstein","sequence":"first","affiliation":[{"name":"Computer Science Department, University of Haifa, 199 Aba Khoushy Ave., Mount Carmel, Haifa, P.C. 3498838, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7700-9711","authenticated-orcid":false,"given":"Dan","family":"Feldman","sequence":"additional","affiliation":[{"name":"Computer Science Department, University of Haifa, 199 Aba Khoushy Ave., Mount Carmel, Haifa, P.C. 3498838, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2020,7,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Geiger, A., Lenz, P., and Urtasun, R. (2012, January 16\u201321). Are we ready for autonomous driving? The kitti vision benchmark suite. Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Providence, RI, USA.","DOI":"10.1109\/CVPR.2012.6248074"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Xu, W., Snider, J., Wei, J., and Dolan, J.M. (July, January 28). Context-aware tracking of moving objects for distance keeping. Proceedings of the 2015 IEEE on Intelligent Vehicles Symposium (IV), Seoul, South Korea.","DOI":"10.1109\/IVS.2015.7225908"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s10846-008-9235-4","article-title":"Visual navigation for mobile robots: A survey","volume":"53","author":"Ortiz","year":"2008","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1111\/cgf.12720","article-title":"Planar shape detection and regularization in tandem","volume":"Volume 35","author":"Oesau","year":"2016","journal-title":"Computer Graphics Forum"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1111\/cgf.12790","article-title":"Data-driven shape analysis and processing","volume":"Volume 36","author":"Xu","year":"2017","journal-title":"Computer Graphics Forum"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/j.conbuildmat.2018.03.246","article-title":"Evaluation of granular particle roundness using digital image processing and computational geometry","volume":"172","author":"Zhihong","year":"2018","journal-title":"Constr. Build. Mater."},{"key":"ref_7","unstructured":"Titsias, M.K. (2017). Learning model reparametrizations: Implicit variational inference by fitting mcmc distributions. arXiv."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10994-018-5710-8","article-title":"Meta-Interpretive Learning from noisy images","volume":"107","author":"Muggleton","year":"2018","journal-title":"Mach. Learn."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Omran, M., Lassner, C., Pons-Moll, G., Gehler, P., and Schiele, B. (2018, January 5\u20138). Neural body fitting: Unifying deep learning and model based human pose and shape estimation. Proceedings of the 2018 International Conference on 3D Vision (3DV), Verona, Italy.","DOI":"10.1109\/3DV.2018.00062"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Estellers, V., Schmidt, F., and Cremers, D. (2018, January 5\u20138). Robust Fitting of Subdivision Surfaces for Smooth Shape Analysis. Proceedings of the 2018 International Conference on 3D Vision (3DV), Verona, Italy.","DOI":"10.1109\/3DV.2018.00040"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1109\/LRA.2017.2773668","article-title":"Quadcopter Tracks Quadcopter via Real Time Shape Fitting","volume":"3","author":"Epstein","year":"2018","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_12","unstructured":"(2019, March 10). acegif.com. Pulsating Ring of Fire. Available online: https:\/\/acegif.com\/fire-on-gifs."},{"key":"ref_13","unstructured":"VC, H.P. (1962). Method and Means for Recognizing Complex Patterns. (3,069,654), US Patent."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1124","DOI":"10.1049\/iet-ipr.2010.0499","article-title":"Fast algorithm for multiple-circle detection on images using learning automata","volume":"6","author":"Cuevas","year":"2012","journal-title":"IET Image Process."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1016\/j.patcog.2012.09.020","article-title":"EDCircles: A real-time circle detector with a false detection control","volume":"46","author":"Akinlar","year":"2013","journal-title":"Pattern Recognit."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2359","DOI":"10.1016\/j.asr.2016.03.026","article-title":"An efficient circle detector not relying on edge detection","volume":"57","author":"Cai","year":"2016","journal-title":"Adv. Space Res."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Zhou, X., Wang, Y., Zhu, Q., and Miao, Z. (2016). Circular object detection in polar coordinates for 2D LIDAR data. Chinese Conference on Pattern Recognition, Springer.","DOI":"10.1007\/978-981-10-3002-4_6"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.patcog.2015.12.004","article-title":"A fast and robust circle detection method using isosceles triangles sampling","volume":"54","author":"Zhang","year":"2016","journal-title":"Pattern Recognit."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1755006","DOI":"10.1142\/S0218001417550060","article-title":"Fast circle detection using spatial decomposition of Hough transform","volume":"31","author":"Zhou","year":"2017","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.eswa.2015.11.018","article-title":"On circular traffic sign detection and recognition","volume":"48","author":"Berkaya","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s10044-017-0623-x","article-title":"EDTriangles: A high-speed triangle detection algorithm with a false detection control","volume":"21","author":"Berkaya","year":"2018","journal-title":"Pattern Anal. Appl."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Bae, J., Cho, H., and Yoo, H. (2018, January 1\u20133). Geometric symmetry using rotational scanning method for circular form detection. Proceedings of the 2018 IEEE 9th Annual Information Technology, Electronics and Mobile Communication Conference (IEMCON), Vancouver, BC, Canada.","DOI":"10.1109\/IEMCON.2018.8614934"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1145\/358669.358692","article-title":"Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography","volume":"24","author":"Fischler","year":"1981","journal-title":"Commun. ACM"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1877","DOI":"10.1007\/s00138-014-0640-3","article-title":"3D Hough transform for sphere recognition on point clouds","volume":"25","author":"Camurri","year":"2014","journal-title":"Mach. Vis. Appl."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1205","DOI":"10.1007\/s00371-015-1157-0","article-title":"eSphere: Extracting spheres from unorganized point clouds","volume":"32","author":"Tran","year":"2016","journal-title":"Vis. Comput."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Feldman, D. (2020). Core-Sets: Updated Survey. Sampling Techniques for Supervised or Unsupervised Tasks, Springer.","DOI":"10.1007\/978-3-030-29349-9_2"},{"key":"ref_27","unstructured":"Jubran, I., Maalouf, A., and Feldman, D. (2019). Introduction to Coresets: Accurate Coresets. arXiv."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Har-Peled, S. (2006, January 5\u20137). How to get close to the median shape. Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, Sedona, AZ, USA.","DOI":"10.1145\/1137856.1137915"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1145\/1008731.1008736","article-title":"Approximating extent measures of points","volume":"51","author":"Agarwal","year":"2004","journal-title":"J. ACM (JACM)"},{"key":"ref_30","unstructured":"Maalouf, A., Jubran, I., and Feldman, D. (2019). Fast and Accurate Least-Mean-Squares Solvers. arXiv."},{"key":"ref_31","unstructured":"Maple, M. (2018, March 21). A Division of Waterloo Maple Inc. Waterloo, Ontario. Available online: https:\/\/www.maplesoft.com."},{"key":"ref_32","unstructured":"Inc., W.R. (2019, April 16). Mathematica, Version 12.0. Available online: https:\/\/www.wolfram.com."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Langberg, M., and Schulman, L.J. (2010, January 17\u201319). Universal \u03b5-approximators for integrals. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA.","DOI":"10.1137\/1.9781611973075.50"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Feldman, D., and Langberg, M. (2011, January 6\u20138). A unified framework for approximating and clustering data. Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, San Jose, CA, USA.","DOI":"10.1145\/1993636.1993712"},{"key":"ref_35","unstructured":"Braverman, V., Feldman, D., and Lang, H. (2016). New frameworks for offline and streaming coreset constructions. arXiv."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Vapnik, V.N., and Chervonenkis, A.Y. (2015). On the uniform convergence of relative frequencies of events to their probabilities. Measures of Complexity, Springer.","DOI":"10.1007\/978-3-319-21852-6_3"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Varadarajan, K., and Xiao, X. (2012, January 17\u201319). A near-linear algorithm for projective clustering integer points. Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Kyoto, Japan.","DOI":"10.1137\/1.9781611973099.105"},{"key":"ref_38","unstructured":"Van Rossum, G., and Drake, F.L. (1995). Python Tutorial, Centrum voor Wiskunde en Informatica."},{"key":"ref_39","unstructured":"Oliphant, T.E. A Guide to NumPy, Trelgol Publishing. Available online: https:\/\/www.numpy.org."},{"key":"ref_40","unstructured":"Millman, K.J., and Aivazis, M. Python for Scientists and Engineers, Computing in Science and Engineering, University of California. Available online: https:\/\/www.scipy.org."},{"key":"ref_41","unstructured":"Team, O.D. (2019, November 12). OpenCV API Reference 2015. Version 3.4.8. Available online: https:\/\/docs.opencv.org\/releases."},{"key":"ref_42","unstructured":"(2020, July 18). Available online: https:\/\/github.com\/depste01\/SphereFitting."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1600578","DOI":"10.1002\/adem.201600578","article-title":"Nano-and Micro-Mechanical Properties of Ultrafine-Grained Materials Processed by Severe Plastic Deformation Techniques","volume":"19","author":"Kawasaki","year":"2017","journal-title":"Adv. Eng. Mater."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1800029","DOI":"10.1002\/adem.201800029","article-title":"Microarchitected stretching-dominated mechanical metamaterials with minimal surface topologies","volume":"20","author":"Rezgui","year":"2018","journal-title":"Adv. Eng. Mater."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1700625","DOI":"10.1002\/adem.201700625","article-title":"High-Entropy Alloy (HEA)-Coated Nanolattice Structures and Their Mechanical Properties","volume":"20","author":"Gao","year":"2018","journal-title":"Adv. Eng. Mater."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/8\/177\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:50:46Z","timestamp":1760176246000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/8\/177"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,22]]},"references-count":45,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2020,8]]}},"alternative-id":["a13080177"],"URL":"https:\/\/doi.org\/10.3390\/a13080177","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,22]]}}}