2026-09-18T23:10:16Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/69422 2023-07-11 col_2142_5131 col_2142_8888 com_2142_5130 com_2142_8887 com_2142_234

Preparata, Franco P. Tamassia, Roberto 2014-12-15T19:05:43Z 2014-12-15T19:05:43Z 10000-01-01 1988 1988 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. Made available in DSpace on 2014-12-15T19:05:43Z (GMT). No. of bitstreams: 1 8908863.pdf: 5573573 bytes, checksum: 73e737dea79cb47db083c72bf65fdc59 (MD5) Previous issue date: 1988 Embargo set by: Seth Robbins for item 69588 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs U of I Only 142 p. Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988. http://hdl.handle.net/2142/69422 (UMI)AAI8908863 Computer Science Dynamic Data Structures for Two Dimensional Searching text Electrical Engineering Electrical Engineering University of Illinois at Urbana-Champaign Dissertation Ph.D.