2026-09-22T11:18:58Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/108541 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Har-Peled, Sariel Rajgopal, - 2020-10-07T21:00:10Z 2020-10-07T21:00:10Z 2020-07-24 2020-08 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 application/pdf http://hdl.handle.net/2142/108541 en Copyright 2020 - Rajgopal Voronoi diagrams CGAL Computational Geometry Shortest secure path in a Voronoi Diagram text Thesis Computer Science Computer Science University of Illinois at Urbana-Champaign Thesis M.S.