{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T13:58:39Z","timestamp":1779890319024,"version":"3.53.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2009,7,27]],"date-time":"2009-07-27T00:00:00Z","timestamp":1248652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003561","name":"Ministry of Culture, Sports and Tourism","doi-asserted-by":"publisher","award":["2008-F-033-02"],"award-info":[{"award-number":["2008-F-033-02"]}],"id":[{"id":"10.13039\/501100003561","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["KRF-2007-331-D00400"],"award-info":[{"award-number":["KRF-2007-331-D00400"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002994","name":"Ministry of Knowledge Economy","doi-asserted-by":"publisher","award":["2008-F-033-02"],"award-info":[{"award-number":["2008-F-033-02"]}],"id":[{"id":"10.13039\/501100002994","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2009,7,27]]},"abstract":"<jats:p>We present a simple algorithm to compute the Hausdorff distance between complicated, polygonal models at interactive rates. The algorithm requires no assumptions about the underlying topology and geometry. To avoid the high computational and implementation complexity of exact Hausdorff distance calculation, we approximate the Hausdorff distance within a user-specified error bound. The main ingredient of our approximation algorithm is a novel polygon subdivision scheme, called<jats:italic>Voronoi subdivision<\/jats:italic>, combined with culling between the models based on bounding volume hierarchy (BVH). This<jats:italic>cross-culling<\/jats:italic>method relies on tight yet simple computation of bounds on the Hausdorff distance, and it discards unnecessary polygon pairs from each of the input models alternatively based on the distance bounds. This algorithm can approximate the Hausdorff distance between polygonal models consisting of tens of thousands triangles with a small error bound in real-time, and outperforms the existing algorithm by more than an order of magnitude. We apply our Hausdorff distance algorithm to the measurement of shape similarity, and the computation of penetration depth for physically-based animation. In particular, the penetration depth computation using Hausdorff distance runs at highly interactive rates for complicated dynamics scene.<\/jats:p>","DOI":"10.1145\/1531326.1531380","type":"journal-article","created":{"date-parts":[[2009,7,28]],"date-time":"2009-07-28T12:43:55Z","timestamp":1248785035000},"page":"1-9","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["Interactive Hausdorff distance computation for general polygonal models"],"prefix":"10.1145","volume":"28","author":[{"given":"Min","family":"Tang","sequence":"first","affiliation":[{"name":"Ewha Womans University, Seoul, Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minkyoung","family":"Lee","sequence":"additional","affiliation":[{"name":"Ewha Womans University, Seoul, Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Young J.","family":"Kim","sequence":"additional","affiliation":[{"name":"Ewha Womans University, Seoul, Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,7,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/777792.777835"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2003.1175093"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Alt H. and Guibas L. J. 2000. Discrete geometric shapes: Matching interpolation and approximation. In Handbook of Computational Geometry J.-R. Sack and J. Urrutia Eds. Elsevier Science Publishers B. V. North-Holland Amsterdam 121--153. Alt H. and Guibas L. J. 2000. Discrete geometric shapes: Matching interpolation and approximation. In Handbook of Computational Geometry J.-R. Sack and J. Urrutia Eds. Elsevier Science Publishers B. V. North-Holland Amsterdam 121--153.","DOI":"10.1016\/B978-044482537-7\/50004-8"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530830"},{"key":"e_1_2_2_5_1","volume-title":"Discrete and Computational Geometry.","volume":"25","author":"Alt H."},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the IEEE International Conference on Multi-media and Expo, 705--708","author":"Aspert N."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90042-X"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00047-X"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00236"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237220"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Ehmann S. and Lin M. C. 2001. Accurate and fast proximity queries between polyhedra using convex surface decomposition. Computer Graphics Forum (Proc. of Eurographics'2001) 20 3 500--510. Ehmann S. and Lin M. C. 2001. Accurate and fast proximity queries between polyhedra using convex surface decomposition. Computer Graphics Forum (Proc. of Eurographics'2001) 20 3 500--510.","DOI":"10.1111\/1467-8659.00543"},{"key":"e_1_2_2_12_1","volume-title":"Proc. of IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Fisher S.","year":"2001"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/258734.258849"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.761267"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1201775.882358"},{"key":"e_1_2_2_17_1","volume-title":"International Conferences in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG), 41--48","author":"Guthe M."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11044-004-2513-4"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/142675.142700"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189323"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.232073"},{"key":"e_1_2_2_22_1","series-title":"Lecture Notes in Computer Science, 90--95","volume-title":"Robust face detection using the Hausdorff distance","author":"Jesorsky O."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.06.003"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/545261.545266"},{"key":"e_1_2_2_25_1","volume-title":"Proc. of IEEE Int. Conference on Robotics and Automation.","author":"Larsen E."},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Lin M. and Manocha D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry. Lin M. and Manocha D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry .","DOI":"10.1201\/9781420035315.ch35"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-005-4560-z"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.01.010"},{"key":"e_1_2_2_29_1","doi-asserted-by":"crossref","unstructured":"Luebke D. Watson B. Cohen J. Reddy M. and Varshney A. 2002. Level of detail for 3D graphics. Elsevier Science Inc. New York NY USA. Luebke D. Watson B. Cohen J. Reddy M. and Varshney A. 2002. Level of detail for 3D graphics . Elsevier Science Inc. New York NY USA.","DOI":"10.1016\/B978-155860838-2\/50003-0"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/54852.378528"},{"key":"e_1_2_2_31_1","unstructured":"NVIDIA. 2009. PhysX. http:\/\/www.nvidia.com. NVIDIA. 2009. PhysX. http:\/\/www.nvidia.com."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10055-004-0138-9"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02716804"},{"key":"e_1_2_2_34_1","unstructured":"Tang M. and Kim Y. J. 2009. Deriving upper and lower bounds of Hausdorff distance for polygonal models. Tech. rep. CSE-TR-2009-01 Ewha Womans University Seoul Korea. Tang M. and Kim Y. J. 2009. Deriving upper and lower bounds of Hausdorff distance for polygonal models. Tech. rep. CSE-TR-2009-01 Ewha Womans University Seoul Korea."},{"key":"e_1_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Varadhan G. and Manocha D. 2004. Accurate Minkowski sum approximation of polyhedral models. In Pacific Graphics 392--401. Varadhan G. and Manocha D. 2004. Accurate Minkowski sum approximation of polyhedral models. In Pacific Graphics 392--401.","DOI":"10.1109\/PCCGA.2004.1348370"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189762.1206075"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2007.05.012"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0262-8856(03)00137-9"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1531326.1531380","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1531326.1531380","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:12Z","timestamp":1750249392000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1531326.1531380"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,27]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,7,27]]}},"alternative-id":["10.1145\/1531326.1531380"],"URL":"https:\/\/doi.org\/10.1145\/1531326.1531380","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7,27]]},"assertion":[{"value":"2009-07-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}