A Data Structure to Efficiently Answer Point Location Queries with Respect to a Line

Abstract

A basic question in computational geometry is to find the relationship between a set of points and a line in the real plane. In this paper, we present multidimensional data structures for N points that allow answering in O(log N + k) time the following queries: (1) Given an input line, estimate the number of points below the line, (2) Given an input line, return the k ≤ N points that are below the line, and (3) Given an input line, return the point that is closest to the line.