Shortest secure path in a Voronoi Diagram

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2020

Author dc:creator

• Rajgopal, -

Contributors dc:contributor

• Har-Peled, Sariel

• Voronoi diagrams
• CGAL
• Computational Geometry

Statement dc:rights

• Copyright 2020 - Rajgopal

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/108541

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/108541