## Files in this item

FilesDescriptionFormat

application/pdf

8908863.pdf (6MB)
(no description provided)PDF

## Description

 Title: Dynamic Data Structures for Two Dimensional Searching Author(s): Tamassia, Roberto Doctoral Committee Chair(s): Preparata, Franco P. Department / Program: Electrical Engineering Discipline: Electrical Engineering Degree Granting Institution: University of Illinois at Urbana-Champaign Degree: Ph.D. Genre: Dissertation Subject(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. Issue Date: 1988 Type: Text Description: 142 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988. URI: http://hdl.handle.net/2142/69422 Other Identifier(s): (UMI)AAI8908863 Date Available in IDEALS: 2014-12-15 Date Deposited: 1988
﻿