{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T11:55:01Z","timestamp":1759838101420,"version":"3.41.2"},"reference-count":39,"publisher":"ASME International","issue":"4","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,12,1]]},"abstract":"<jats:p>There has been much attention on sophisticated algorithm design to compute geometric arrangements with both time and space efficiency. The issue of robustness and reliability has also been the subject of some interest, although mostly at the level of theory rather than practice and commercial grade implementation. What seems to have received very little attention is the need to prepare the data for successful processing. It is almost universally assumed that the data are valid and well presented and the only real challenge is to come up with a clever way of computing the results with progressively smaller time and space bounds. The aim of this paper is to narrow this gap by focusing entirely on input data anomalies, how to prepare the data for error free computation and how to post process the results for dowstream computing. The medial axis computation, using VRONI (Held, 2001, \u201cVRONI: An Engineering Approach to the Reliable and Efficient Computation of Voronoi Diagram of Points and Line Segments,\u201d Comput. Geom.\u2014Theory Appl., 18, pp. 95\u2013123), is singled out as an example and it is shown that based on how the data are prepared, the results can be vastly different. We argue in this paper that the success of geometric computing depends equally on algorithm design as well as on data processing. VRONI (and most geometric algorithms) does not understand the concept of noise, gaps, or aliasing. It only sees a polygon and generates the medial axis accordingly. It is the job of the applications engineer to prepare the data so that the output is acceptable.<\/jats:p>","DOI":"10.1115\/1.4027991","type":"journal-article","created":{"date-parts":[[2014,7,10]],"date-time":"2014-07-10T15:31:45Z","timestamp":1405006305000},"update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":1,"title":["Data Processing for Medial Axis Computation Using B-Spline Smoothing"],"prefix":"10.1115","volume":"14","author":[{"given":"Les A.","family":"Piegl","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of South Florida, Tampa, FL 33620 e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Parikshit","family":"Kulkarni","sequence":"additional","affiliation":[{"name":"Synopsys, Inc., Mountain View, CA 94043 e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Khairan","family":"Rajab","sequence":"additional","affiliation":[{"name":"College of Computer Science and Information Systems, Najran University, Najran 61441, Saudi Arabia e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2014,9,1]]},"reference":[{"issue":"2","key":"2019100601155610900_B1","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/S0925-7721(01)00003-7","article-title":"VRONI: An Engineering Approach to the Reliable and Efficient Computation of Voronoi Diagram of Points and Line Segments","volume":"18","year":"2001","journal-title":"Comput. Geom.\u2014Theory Appl."},{"issue":"5","key":"2019100601155610900_B2","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1080\/16864360.2005.10738333","article-title":"Knowledge-Guided Computation for Robust CAD","volume":"2","year":"2005","journal-title":"Comput-Aided Des. Appl."},{"key":"2019100601155610900_B3","first-page":"362","article-title":"A Transformation for Extracting New Descriptors of Shape","volume-title":"Models for Perception of Speech and Visual Form","year":"1967"},{"issue":"2","key":"2019100601155610900_B4","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s00366-011-0250-x","article-title":"A Simple Algorithm for the Medial Axis Transform Computation","volume":"29","year":"2013","journal-title":"Eng. Comput."},{"key":"2019100601155610900_B5","doi-asserted-by":"crossref","unstructured":"Chin, F., Snoeyink, J., and Wang, C.-A., 1995, \u201cFinding the Medial Axis of a Simple Polygon in Linear Time,\u201d Proceedings of the 6th Annual International Symposium Algorithms Computational, Lecture Notes in Computer Science, Springer-Verlag, Vol. 1004, pp. 382\u2013391.","DOI":"10.1007\/BFb0015444"},{"issue":"4","key":"2019100601155610900_B6","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1109\/TPAMI.1982.4767267","article-title":"Medial Axis Transformation of a Plane Shape","volume":"PAMI-4","year":"1982","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell"},{"key":"2019100601155610900_B7","doi-asserted-by":"crossref","unstructured":"Preparata, F. P., 1977, \u201cThe Medial Axis of a Simple Polygon,\u201d Proceedings of the 6th Mathematics Foundation of Computer Science, Lecture Notes in Computer Science, Springer-Verlag, Vol. 53, pp. 443\u2013450.","DOI":"10.1007\/3-540-08353-7_166"},{"issue":"3","key":"2019100601155610900_B8","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1006\/cviu.1997.0536","article-title":"Computing and Simplifying 2D and 2D Continuous Skeletons","volume":"67","year":"1997","journal-title":"Comput. Vision Image Understanding"},{"issue":"3","key":"2019100601155610900_B9","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/1049-9660(92)90030-7","article-title":"Continuous Skeleton Computation by Voronoi Diagram","volume":"55","year":"1992","journal-title":"CVGIP: Image Understanding"},{"issue":"1","key":"2019100601155610900_B10","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1006\/ciun.1994.1007","article-title":"Convergence and Continuity Criteria for Discrete Approximation of the Continuous Planar Skeletons","volume":"59","year":"1994","journal-title":"CVGIP: Image Understanding"},{"issue":"1","key":"2019100601155610900_B11","first-page":"179","article-title":"Approximating the Medial Axis From the Voronoi Diagram With a Convergence Guarantee","volume":"38","year":"2003","journal-title":"Algorithmica"},{"issue":"2","key":"2019100601155610900_B12","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/S0010-4485(03)00061-7","article-title":"Approximate Medial Axis as a Voronoi Subcomplex","volume":"36","year":"2004","journal-title":"Comput.-Aided Des."},{"issue":"1","key":"2019100601155610900_B13","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1023\/A:1020722624682","article-title":"On Voronoi Diagrams and Medial Axes","volume":"17","year":"2002","journal-title":"J. Math. Imaging Vision"},{"issue":"1\u20132","key":"2019100601155610900_B14","first-page":"51","article-title":"A Straightforward Algorithm for Computing the Medial Axis of a Simple Polygon","volume":"39","year":"1991","journal-title":"Int. J. Comput. Math."},{"issue":"1","key":"2019100601155610900_B15","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1109\/2945.489387","article-title":"Shape Description by Medial Axis Construction","volume":"2","year":"1996","journal-title":"IEEE Trans. Visualization Comput. Graph."},{"issue":"12","key":"2019100601155610900_B16","doi-asserted-by":"crossref","first-page":"1050","DOI":"10.1016\/j.cad.2009.08.005","article-title":"Medial Axis of a Planar Shape by Offset Self-Intersection","volume":"41","year":"2009","journal-title":"Comput.-Aided Des."},{"key":"2019100601155610900_B17","doi-asserted-by":"crossref","unstructured":"Culver, T., Keyser, J., and Manocha, D., 1999, \u201cAccurate Computation of the Medial Axis of a Polyhedron,\u201d Proceedings of the Solid Modeling\u201999, pp. 179\u2013190.","DOI":"10.1145\/304012.304030"},{"key":"2019100601155610900_B18","unstructured":"Hoffman, C., 1990, \u201cHow to Construct the Skeleton of CSG Objects,\u201d Proceedings of Fourth IMA Conference the Mathematics of Surfaces, A.Bowyer and J.Davenport, eds., University of Bath, UK."},{"issue":"5","key":"2019100601155610900_B19","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/j.cad.2008.08.008","article-title":"Medial Axis Computation for Planar Free-Form Shapes","volume":"41","year":"2009","journal-title":"Comput.-Aided Des."},{"issue":"2","key":"2019100601155610900_B20","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/j.cad.2004.05.008","article-title":"MATHSM: Medial Axis Transform Toward High Speed Machining of Pockets","volume":"37","year":"2005","journal-title":"Comput.-Aided Des."},{"issue":"6","key":"2019100601155610900_B21","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1006\/gmip.1997.0444","article-title":"A New Algorithm for Medial Axis Transform of Plane Domain","volume":"59","year":"1997","journal-title":"Graph. Models Image Process."},{"issue":"1","key":"2019100601155610900_B22","doi-asserted-by":"crossref","first-page":"57","DOI":"10.2140\/pjm.1997.181.57","article-title":"Mathematical Theory of the Medial Axis Transform","volume":"181","year":"1997","journal-title":"Pac. J. Math."},{"issue":"5\u20136","key":"2019100601155610900_B23","first-page":"577","article-title":"Stable Computation of the 2D Medial Axis Transform","volume":"8","year":"1998","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"4","key":"2019100601155610900_B24","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1115\/1.1631582","article-title":"Efficient Computation of a Simplified Medial Axis","volume":"3","year":"2003","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"issue":"7","key":"2019100601155610900_B25","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1016\/j.cagd.2004.03.005","article-title":"Exploiting Curvatures to Compute the Medial Axis for Domains With Smooth Boundary","volume":"21","year":"2004","journal-title":"Comput. Aided Geom. Des."},{"issue":"4","key":"2019100601155610900_B26","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1016\/j.cad.2008.01.002","article-title":"Computation of Medial Axis and Offset Curves of Curved Boundaries in Planar Domains","volume":"40","year":"2008","journal-title":"Comput.-Aided Des."},{"issue":"4","key":"2019100601155610900_B27","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1016\/j.cagd.2009.01.002","article-title":"Computation of Medial Axis and Offset Curves of Curved Boundaries in Planar Domains Based on the Cesaro's Approach","volume":"26","year":"2009","journal-title":"Comput. Aided Geom. Des."},{"issue":"8","key":"2019100601155610900_B28","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1016\/j.cad.2011.03.001","article-title":"Computation of the Medial Axis of Planar Domains Based on Saddle Point Programming","volume":"43","year":"2011","journal-title":"Comput.-Aided Des."},{"issue":"7","key":"2019100601155610900_B29","first-page":"619","article-title":"Constructing Medial Axis Transform of Planar Domains With Curved Boundaries","volume":"35","year":"2002","journal-title":"Comput.-Aided Des."},{"key":"2019100601155610900_B30","unstructured":"Vermeer, P. J., 1994, \u201cMedial Axis Transform to Boundary Representation Conversion,\u201d Ph.D. thesis, Purdue University, West Lafayette, IN."},{"issue":"6","key":"2019100601155610900_B31","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1016\/S0167-8396(98)00007-7","article-title":"Degenerate Point\/Curve and Curve\/Curve Bisectors Arising in Medial Axis Computations for Planar Domains With Curved Boundaries","volume":"15","year":"1998","journal-title":"Comput.-Aided Geom. Des."},{"issue":"1","key":"2019100601155610900_B32","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0377-0427(98)00211-8","article-title":"Voronoi Diagram and Medial Axis Algorithm for Planar Domains With Curved Boundaries\u2014I: Theoretical Foundations","volume":"102","year":"1999","journal-title":"J. Comput. Appl. Math."},{"issue":"2","key":"2019100601155610900_B33","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/S0377-0427(98)00223-4","article-title":"Voronoi Diagram and Medial Axis Algorithm for Planar Domains With Curved Boundaries\u2014II: Detailed Algorithm Description","volume":"102","year":"1999","journal-title":"J. Comput. Appl. Math."},{"volume-title":"The NURBS Book","year":"1997","key":"2019100601155610900_B34"},{"issue":"2","key":"2019100601155610900_B35","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/PL00007188","article-title":"Least-Squares NURBS Curve Fitting With Arbitrary End Derivatives","volume":"16","year":"2000","journal-title":"Eng. Comput."},{"key":"2019100601155610900_B36","doi-asserted-by":"crossref","unstructured":"Artaechevarria, X., Mu\u00f1oz-Barrutia, A., and Ortiz de Solorzano, C., 2007, \u201cRestoration of Biomedical Images Using Locally Adaptive B-Spline Smoothing,\u201d IEEE International Conference on Image Processing, ICIP 2007, San Antonio, TX, Sept. 16\u201319, pp. 425\u2013428.10.1109\/ICIP.2007.4379183","DOI":"10.1109\/ICIP.2007.4379183"},{"issue":"23\u201324","key":"2019100601155610900_B37","first-page":"2021","article-title":"Parameterization of Computational Domain in Isogeometric Analysis: Methods and Comparison","volume":"200","year":"2011","journal-title":"Comput. Methods Appl. Mech. Eng."},{"issue":"5","key":"2019100601155610900_B38","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/j.cad.2008.08.004","article-title":"Topology-Oriented Incremental Computation of Voronoi Diagrams of Circular Arcs and Straight-Line Segments","volume":"41","year":"2009","journal-title":"Comput.-Aided Des."},{"key":"2019100601155610900_B39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.advengsoft.2012.05.006","article-title":"A Fast Algorithm for Constructing Approximate Medial Axis of Polygons Using Steiner Points","volume":"52","year":"2012","journal-title":"Adv. Eng. Software"}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4027991\/6100220\/jcise_014_04_041002.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4027991\/6100220\/jcise_014_04_041002.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,6]],"date-time":"2019-10-06T01:16:40Z","timestamp":1570324600000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/doi\/10.1115\/1.4027991\/371514\/Data-Processing-for-Medial-Axis-Computation-Using"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,1]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,12,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.4027991","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"type":"print","value":"1530-9827"},{"type":"electronic","value":"1944-7078"}],"subject":[],"published":{"date-parts":[[2014,9,1]]},"article-number":"041002"}}