Files in this item



application/pdf8908863.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF


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
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
Description:142 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988.
Other Identifier(s):(UMI)AAI8908863
Date Available in IDEALS:2014-12-15
Date Deposited:1988

This item appears in the following Collection(s)

Item Statistics