Computing closest and farthest points for a query segment

In this paper we present an improved algorithm for finding k closest (farthest) points for a given arbitrary query segment. We show how to preprocess a planar set P of n given points in O(n2logn) expected time (or, alternatively, in O(n2log2n) deterministic time) and a subquadratic space, in order to report k closest points to an arbitrary given query line segment in O(k+log2nloglogn) time. Here, for the first time, the data structure that provides polylogarithmic query time and uses subquadratic space is presented. We also show an algorithm for reporting the k farthest points from an arbitrary given query line segment.