Punto mas cercano y mas lejano

Theoretical Computer Science 393 (2008) 294–300 www.elsevier.com/locate/tcs

Note

Computing closest and farthest points for a query segment
Michael Segal a,∗ , Eli Zeitlin b
a Communication Systems Engineering Department, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel b School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel

Received 6 June 2006; receivedin revised form 20 November 2007; accepted 22 November 2007

Communicated by G. Ausiello

Abstract 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(n 2 log n) expected time (or, alternatively, in O(n 2 log2 n) deterministic time) and a subquadratic space, inorder to report k closest points to an arbitrary given query line segment in O(k + log2 n log log n) 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. c 2007 Elsevier B.V. All rights reserved.
Keywords:Computational geometry; Data structure; Segment dragging problem

1. Introduction We study two proximity problems involving a set P = { p1 , p2 , . . . , pn } of n points in the plane and arbitrary given query line segment. The problems are: 1. k-closest points to an arbitrary query segment: We want to preprocess the set P so that, for a query line segment s, we can report efficiently the k points of Pclosest to s. 2. k-farthest points from an arbitrary query segment: We want to preprocess the set P so that, for a query line segment s, we can report efficiently the k points of P farthest from s. Proximity queries involving line segments have been very little studied. One of the first works of this kind [5] addresses the problem of locating the nearest point to a query straight line segment amonga set of n points in the plane. The following results have been obtained in [5] for a few restricted cases of this problem. • If the query line segment is known to lie outside the convex hull of P, a linear size data structure can be constructed in O(n log n) time, and it finds the nearest neighbor of a line segment in O(log n) time.
∗ Corresponding author. Tel.: +972 8 6472210; fax: +972 86472883.

E-mail addresses: segal@cse.bgu.ac.il (M. Segal), zeitline@post.tau.ac.il (E. Zeitlin). 0304-3975/$ - see front matter c 2007 Elsevier B.V. All rights reserved. doi:10.1016/j.tcs.2007.11.015

M. Segal, E. Zeitlin / Theoretical Computer Science 393 (2008) 294–300

295

• If m non-intersecting query line segments are given simultaneously, then the nearest neighbors of all these linesegments can be reported in O(m log3 n +n log2 n +m log m) time. If n = m, the time complexity can be improved to O(n log2 n) [4]. • When n arbitrary possibly intersecting query line segments are given in advance, then the nearest neighbors of all of them can be reported in O(n 4/3 logk n) time, for some constant k [3]. A slightly better result, with running time ∗ O(n 4/3 2 O(log n) ), is proposedin [4]. √ • If n query line segments arrive online, then the amortized query time per segment is O( n logk n), for some constant k. We consider an unrestricted version of the k nearest (farthest) points query problem for line segments, where the objective is to report the k nearest (farthest) points of an arbitrary query line segment s among a set P of n points. Recently, Goswami et al. [11]presented an algorithm with O(n 2 ) space, O(n 2 log n) expected preprocessing time and O(k + log2 n) query time for the unrestricted version of the problem. Their solution is based on the algorithm for the so-called segment dragging query problem with O(n 2 ) space requirement and O(k + log2 n) query time. This problem was considered initially by Chazelle [7], and asks us to report the first k points...