Range Query Problems in Planar Computational Geometry: Radius of Smallest Enclosing Disk & Generalized Convex Hull

Abstract

Computational geometry is a branch of computer science which deals with computation of geometric functions. It has applications in diverse fields such as computer graphics, robotics, VLSI/chip-design, etc. It has also found real-world applications in software such as maps applications that are used daily by millions of people around the world. Range query problems are a set of problems where a data structure is designed that can pre-process the input set of points so that given a query range, the results of some geometric function over that query range can be computed efficiently. A lot of these problems are non-decomposable, in that the result cannot be computed using the result of the same function on subsets of the query range. These problems are significant today because we have numerous cases of a fixed larger dataset on which different queries are made that need to be answered in the most efficient possible way. Again map software is a great example — updates to the overall map are relatively infrequent, but queries on its data, such as finding distance between two points, are supported at scale. In this thesis, we present results for two different Range Aggregate Query problems in Two Dimensions: Finding the radius of the smallest enclosing disk (Range Aggregate Queries) & Reporting the distinct colours of points on the Convex Hull (Generalized Intersection Searching). Smallest Enclosing Disk Range Query: Let S be a set of n points in the plane. We present a method where, using O(n log2 n) time and space, S can be pre-processed into a data structure such that given an axis-parallel query rectangle q, we can report the radius of the smallest enclosing disk of the points lying in S ∩ q in O(log6 n) time per query. Generalized Convex Hull: We present an output sensitive algorithm for the generalized reporting version of the planar range convex hull problem. Our solutions is in the pointer machine model, for orthogonal range queries on a static point set. We provide a solution for the planar range convex hull problem that answers queries in O(log2 n+c log n) time, using O(n log2 n) space, where n denotes the number of stored points and c the number of colors reported.