Director of Research (if dissertation) or Advisor (if thesis)
Har-Peled, Sariel
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Date of Ingest
2020-10-07T21:00:10Z
Keyword(s)
Voronoi diagrams
CGAL
Computational Geometry
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
