Dynamic Data Structures for Two Dimensional Searching
Tamassia, Roberto
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69422
Description
Title
Dynamic Data Structures for Two Dimensional Searching
Author(s)
Tamassia, Roberto
Issue Date
1988
Doctoral Committee Chair(s)
Preparata, Franco P.
Department of Study
Electrical Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Abstract
In this thesis we investigate dynamic data structures and algorithms for searching in a subdivision of the plane. Three specific problems have been addressed in this area. The first problem, dynamic point location, considers a geometric subdivision of the plane into polygonal regions, and asks for the region that contains a given query point. The second problem, dynamic planar embedding, considers a topological subdivision of the plane induced by a planar embedding of a graph, and asks for a region that contains two given query vertices on its boundary (if one exists). The third problem, dynamic transitive closure, considers a planar acyclic digraph embedded in the plane, and asks for testing the existence of and/or reporting a directed path between two query vertices. In all of the three problems the update operations consist of inserting/deleting vertices and edges. We present several dynamic techniques that improve previously published results in the area. The space requirement ranges from $O$($n$) to $O$($n$ log $n$), and the query and update times range from $O$(log $n$) to $O$(log$\sp2 n$), where $n$ is the size of the subdivision. In addition to their good theoretical space/time performance, all the data structures and algorithms presented are also practical and easy to implement, and therefore suited for real-world applications.
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.
