IIIT Hyderabad Publications 


Range Query Problems in Planar Computational Geometry: Radius of Smallest Enclosing Disk & Generalized Convex HullAuthor: Sankalp Khare Date: 20240702 Report no: IIIT/TH/2024/153 Advisor:Kannan Srinathan AbstractComputational 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/chipdesign, etc. It has also found realworld 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 preprocess 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 nondecomposable, 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 preprocessed into a data structure such that given an axisparallel 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. Full thesis: pdf Centre for Security, Theory and Algorithms 

Copyright © 2009  IIIT Hyderabad. All Rights Reserved. 