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  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  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  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 nδ for some δ > 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  classical randomized auto-partition algorithm can be implemented using a dynamic ray shooting data structure for disjoint polygonal obstacles, yielding a runtime of O([special characters omitted]). 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  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.)
|Advisor:||Souvaine, Diane L.|
|Commitee:||Boghosian, Bruce M., Cowen, Lenore J., Demaine, Erik D., Toth, Csaba D.|
|School Location:||United States -- Massachusetts|
|Source:||DAI-B 71/12, Dissertation Abstracts International|
|Keywords:||Convex partitions, Data structures, Lower bounds, Ray shooting, Simplex emptiness|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be