Planar Convex Hull Range Query and Related Problems
Nadeem Moidu, Jatin Agarwal, Kishore Kothapalli · 2013
We consider the planar convex hull range query prob-lem. Let P be a set of points in the plane. We prepro-cess these points into a data structure such that given an orthogonal range query, we can report the convex hull of the points in the range in O(log2 n + h) time, where h is the size of the output. The data structure uses O(n log n) space. This improves the previous bound of O(log5 n+h) time and O(n log2 n) space. Given a range query, it also supports extreme points in a given direc-tion, tangent queries through a given point, and line-hull intersection queries on the points in the range in time O(log2 n) for each orthogonal query and O(log n) time for each additional query on that range. These problems have not been studied before. 1