{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/108541"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/108541","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Shortest secure path in a Voronoi Diagram","abstract":"We investigate the problem of computing the shortest secure path in a Voronoi diagram. Here, a path is secure if it is a sequence of touching Voronoi cells, where each Voronoi cell in the path has a uniform cost of being secured. Importantly, we allow inserting new sites, which in some cases leads to significantly shorter paths. We present an O(nlogn) time algorithm for solving this problem in the plane, which uses a dynamic additive weighted Voronoi diagram to compute this path. The algorithm is an interesting combination of the continuous and discrete Dijkstra algorithms. We also implemented the algorithm using CGAL.","abstract_html":"We investigate the problem of computing the shortest secure path in a Voronoi diagram. Here, a path is secure if it is a sequence of touching Voronoi cells, where each Voronoi cell in the path has a uniform cost of being secured. Importantly, we allow inserting new sites, which in some cases leads to significantly shorter paths. We present an O(nlogn) time algorithm for solving this problem in the plane, which uses a dynamic additive weighted Voronoi diagram to compute this path. The algorithm is an interesting combination of the continuous and discrete Dijkstra algorithms. We also implemented the algorithm using CGAL.","abstract_has_math":false,"creators":["Rajgopal, -"],"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":2020,"date_issued":"2020-10-07T21:00:10Z","date_published":"2020-10-07T21:00:10Z","updated_at":"2026-07-22T22:24:48Z","subjects":["Voronoi diagrams","CGAL","Computational Geometry"],"languages":["en"],"rights":["Copyright 2020 - Rajgopal"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/108541","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":["Rajgopal, -"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-10-07T21:00:10Z","2020-07-24","2020-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"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":["Voronoi diagrams","CGAL","Computational Geometry"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2020 - Rajgopal"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/108541"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We investigate the problem of computing the shortest secure path in a Voronoi diagram. Here, a path is secure if it is a sequence of touching Voronoi cells, where each Voronoi cell in the path has a uniform cost of being secured. Importantly, we allow inserting new sites, which in some cases leads to significantly shorter paths. We present an O(nlogn) time algorithm for solving this problem in the plane, which uses a dynamic additive weighted Voronoi diagram to compute this path. The algorithm is an interesting combination of the continuous and discrete Dijkstra algorithms. We also implemented the algorithm using CGAL.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-10-02 without embargo terms","The student, - Rajgopal, accepted the attached license on 2020-07-23 at 11:33.","The student, - Rajgopal, submitted this Thesis for approval on 2020-07-23 at 11:57.","This Thesis was approved for publication on 2020-07-24 at 09:17.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15736 on 2020-10-02 at 15:15:22","Made available in DSpace on 2020-10-07T21:00:10Z (GMT). No. of bitstreams: 2 RAJGOPAL-THESIS-2020.pdf: 16119375 bytes, checksum: 18d0f8bbdede94cfa7e5dd216f6aa487 (MD5) LICENSE.txt: 4207 bytes, checksum: ad83c32ab92ead75e6ea8024818b4779 (MD5) Previous issue date: 2020-07-24"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Shortest secure path in a Voronoi Diagram"]}]}],"canonical_facts":{"dc:contributor":["Har-Peled, Sariel"],"dc:creator":["Rajgopal, -"],"dc:date":["2020-10-07T21:00:10Z","2020-07-24","2020-08"],"dc:description":["We investigate the problem of computing the shortest secure path in a Voronoi diagram. Here, a path is secure if it is a sequence of touching Voronoi cells, where each Voronoi cell in the path has a uniform cost of being secured. Importantly, we allow inserting new sites, which in some cases leads to significantly shorter paths. We present an O(nlogn) time algorithm for solving this problem in the plane, which uses a dynamic additive weighted Voronoi diagram to compute this path. The algorithm is an interesting combination of the continuous and discrete Dijkstra algorithms. We also implemented the algorithm using CGAL.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-10-02 without embargo terms","The student, - Rajgopal, accepted the attached license on 2020-07-23 at 11:33.","The student, - Rajgopal, submitted this Thesis for approval on 2020-07-23 at 11:57.","This Thesis was approved for publication on 2020-07-24 at 09:17.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15736 on 2020-10-02 at 15:15:22","Made available in DSpace on 2020-10-07T21:00:10Z (GMT). No. of bitstreams: 2 RAJGOPAL-THESIS-2020.pdf: 16119375 bytes, checksum: 18d0f8bbdede94cfa7e5dd216f6aa487 (MD5) LICENSE.txt: 4207 bytes, checksum: ad83c32ab92ead75e6ea8024818b4779 (MD5) Previous issue date: 2020-07-24"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/108541"],"dc:language":["en"],"dc:rights":["Copyright 2020 - Rajgopal"],"dc:subject":["Voronoi diagrams","CGAL","Computational Geometry"],"dc:title":["Shortest secure path in a Voronoi Diagram"],"dc:type":["text","Thesis"],"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:24:48Z"}