Geometric data structures

In this thesis, we prove new lower bounds for simplex emptiness queries in the partition graph model. Our lower bounds are based on the lower bounds provided by Erickson [40] for online hyperplane emptiness problem in the partition graph model, and are within a polylogarithmic factor of the optimal in the plane. Previously known lower bounds for simplex emptiness were based on the rather weak lower bounds due to Erickson [40] for halfspace emptiness in the partition graph model (only trivial lower bounds were known for 2 ≤ d ≤ 4). Our lower bounds automatically imply lower bounds for simplex range reporting, where a data structure needs to report all r points contained in the query simplex. Chazelle and Rosenberg [34] had previously established lower bounds for simplex range reporting in the pointer machine model, but unfortunately their lower bounds only hold for the case when r is at least ndelta for some delta > 0. Our lower bounds apply to host of other important problems such as point-inclusion in union of slabs, segment intersection searching, implicit point location, line-nearest neighbor and segment dragging queries etc.;Although these lower bounds make it impossible to create efficient data structures for various geometric problems, these data structures are not used in isolation but by specific algorithms. These algorithms may generate a sequence of queries with some special structure making it possible to beat the lower bounds by designing data structures specific to these algorithms. For example, Paterson and Yao's [64] classical randomized auto-partition algorithm can be implemented using a dynamic ray shooting data structure for disjoint polygonal obstacles, yielding a runtime of O( n32 lgn ). Since the algorithm does not "really need" a general ray shooting data structure, we were able to improve the runtime of the algorithm to O(n lg2 n) by developing a new data structure for ray shooting-and-insertion in the free space between disjoint polygonal obstacles. For a ray shooting-and-insertion query, the ray starts at the boundary of some obstacle, and the portion of the ray between the starting point and the first obstacle hit is inserted permanently as a new obstacle. The data structure uses O( n lg n) space and preprocessing time, and it supports m successive ray shooting-and-insertion queries (for sufficiently large m), in O(n lg 2 n + m lg m) total time. For the auto-partitioning algorithm, we perform m = O(n lg n) shooting-and-insertion queries yielding a runtime of O(n lg 2 n).;Finally, we present a useful tool for building data structures---convex partitions with 2-edge connected dual graphs. Convex partitions have proved to be very useful for creating efficient data structures especially in computer graphics. Given a set of convex polygonal obstacles and a bounding box, we may think of the bounding box as a simple polygon and the obstacles as polygonal holes. Then the problem of creating a convex partition becomes that of decomposing the simple polygon with holes into convex parts. Convex polygonal decomposition has received considerable attention in the field of computational geometry. The focus has been to produce a decomposition with as few convex parts as possible. Lingas [59] showed that finding the minimum convex decomposition is NP-hard for polygons with holes. While minimum convex decomposition is desirable, it is not the only criterion for the goodness of a convex partition. Another criterion for the quality of a convex partition might be some property of its dual graph. In this thesis, we give a convex partitioning scheme such that the dual graph of the produced convex partition is 2-edge connected.;The take-away message for the thesis is that we need to create specialized data structures. The idea is not new, and has been pursued before in computer science, however, the existence of severe lower bounds for various geometric problems make the notion even more appealing. (Abstract shortened by UMI.)...