{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/24109"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/24109","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"The Fréchet distance revisited and extended","abstract":"Given two simplicial complexes, and start and end vertices in each complex, we show how to compute curves (in each complex) between these vertices, such that the Frechet distance between these curves is minimized. As a polygonal curve is a complex, this generalizes the regular notion of Frechet distance between curves. We also generalize the algorithm to handle an input of k simplicial complexes. Using this new algorithm we can solve a slew of new problems, from computing a median curve for a given collection of curves, to various motion planning problems. Additionally, we show that for the median curve problem, when the k input curves are c-packed, one can (1+epsilon)-approximate the median curve in near linear time, for fixed k and epsilon.","abstract_html":"Given two simplicial complexes, and start and end vertices in each complex, we show how to compute curves (in each complex) between these vertices, such that the Frechet distance between these curves is minimized. As a polygonal curve is a complex, this generalizes the regular notion of Frechet distance between curves. We also generalize the algorithm to handle an input of k simplicial complexes. Using this new algorithm we can solve a slew of new problems, from computing a median curve for a given collection of curves, to various motion planning problems. Additionally, we show that for the median curve problem, when the k input curves are c-packed, one can (1+epsilon)-approximate the median curve in near linear time, for fixed k and epsilon.","abstract_has_math":false,"creators":["Raichel, Benjamin A."],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Har-Peled, Sariel"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-25T15:03:04Z","date_published":"2011-05-25T15:03:04Z","updated_at":"2026-07-22T22:25:23Z","subjects":["Frechet Distance","Approximation Algorithms","Realistic Input Models"],"languages":["en"],"rights":["Copyright 2011 Benjamin A. Raichel"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/24109","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Har-Peled, Sariel"]},{"key":"dc:creator","label":"Author","values":["Raichel, Benjamin A."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-25T15:03:04Z","2011-05"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Frechet Distance","Approximation Algorithms","Realistic Input Models"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2011 Benjamin A. Raichel"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/24109"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Given two simplicial complexes, and start and end vertices in each complex, we show how to compute curves (in each complex) between these vertices, such that the Frechet distance between these curves is minimized. As a polygonal curve is a complex, this generalizes the regular notion of Frechet distance between curves. We also generalize the algorithm to handle an input of k simplicial complexes. Using this new algorithm we can solve a slew of new problems, from computing a median curve for a given collection of curves, to various motion planning problems. Additionally, we show that for the median curve problem, when the k input curves are c-packed, one can (1+epsilon)-approximate the median curve in near linear time, for fixed k and epsilon.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-03-17T21:40:02Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 frechet3d.tex: 115212 bytes, checksum: 5abf0bc521f7e2be58d8835ecb6ce7e8 (MD5) Raichel_Benjamin.pdf: 494901 bytes, checksum: a548cd46be8e68ae36a87067ec6749ae (MD5)","Made available in DSpace on 2011-05-25T15:03:04Z (GMT). No. of bitstreams: 3 Raichel_Benjamin.pdf: 494901 bytes, checksum: a548cd46be8e68ae36a87067ec6749ae (MD5) license.txt: 4066 bytes, checksum: d7e60b53ce8243274a7e0515c084f392 (MD5) frechet3d.tex: 115212 bytes, checksum: 5abf0bc521f7e2be58d8835ecb6ce7e8 (MD5)"]},{"key":"dc:title","label":"Title","values":["The Fréchet distance revisited and extended"]}]}],"canonical_facts":{"dc:contributor":["Har-Peled, Sariel"],"dc:creator":["Raichel, Benjamin A."],"dc:date":["2011-05-25T15:03:04Z","2011-05"],"dc:description":["Given two simplicial complexes, and start and end vertices in each complex, we show how to compute curves (in each complex) between these vertices, such that the Frechet distance between these curves is minimized. As a polygonal curve is a complex, this generalizes the regular notion of Frechet distance between curves. We also generalize the algorithm to handle an input of k simplicial complexes. Using this new algorithm we can solve a slew of new problems, from computing a median curve for a given collection of curves, to various motion planning problems. Additionally, we show that for the median curve problem, when the k input curves are c-packed, one can (1+epsilon)-approximate the median curve in near linear time, for fixed k and epsilon.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-03-17T21:40:02Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 frechet3d.tex: 115212 bytes, checksum: 5abf0bc521f7e2be58d8835ecb6ce7e8 (MD5) Raichel_Benjamin.pdf: 494901 bytes, checksum: a548cd46be8e68ae36a87067ec6749ae (MD5)","Made available in DSpace on 2011-05-25T15:03:04Z (GMT). No. of bitstreams: 3 Raichel_Benjamin.pdf: 494901 bytes, checksum: a548cd46be8e68ae36a87067ec6749ae (MD5) license.txt: 4066 bytes, checksum: d7e60b53ce8243274a7e0515c084f392 (MD5) frechet3d.tex: 115212 bytes, checksum: 5abf0bc521f7e2be58d8835ecb6ce7e8 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/24109"],"dc:language":["en"],"dc:rights":["Copyright 2011 Benjamin A. Raichel"],"dc:subject":["Frechet Distance","Approximation Algorithms","Realistic Input Models"],"dc:title":["The Fréchet distance revisited and extended"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:23Z"}