Files in this item

FilesDescriptionFormat

application/pdf

application/pdfRAJGOPAL-THESIS-2020.pdf (16MB)
(no description provided)PDF

Description

Title:Shortest secure path in a Voronoi Diagram
Author(s):Rajgopal, -
Advisor(s):Har-Peled, Sariel
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(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.
Issue Date:2020-07-24
Type:Thesis
URI:http://hdl.handle.net/2142/108541
Rights Information:Copyright 2020 - Rajgopal
Date Available in IDEALS:2020-10-07
Date Deposited:2020-08


This item appears in the following Collection(s)

Item Statistics