Dynamic Data Structures for Two Dimensional Searching

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Tamassia, Roberto

Contributors dc:contributor

• Preparata, Franco P.

• Computer Science

Identifier

(UMI)AAI8908863

OAI identifier oai:identifier

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