EFFICIENTLY COMPUTING THE CLOSEST POINT TO A QUERY LINE

Authors
MITRA P CHAUDHURI BB
Citation
P. Mitra et Bb. Chaudhuri, EFFICIENTLY COMPUTING THE CLOSEST POINT TO A QUERY LINE, Pattern recognition letters, 19(11), 1998, pp. 1027-1035
Citations number
8
Categorie Soggetti
Computer Science Artificial Intelligence","Computer Science Artificial Intelligence
Journal title
Pattern recognition letters → ACNP
ISSN journal
01678655
Volume
19
Issue
11
Year of publication
1998
Pages
1027 - 1035
Database
ISI
SICI code
0167-8655(1998)19:11<1027:ECTCPT>2.0.ZU;2-X
Abstract
In this paper we present an algorithm which preprocesses a set of n po ints in O(n log n) time with O(n) space to report the point which has the minimum perpendicular distance from a query line in O(n(0.695)) ti me. When the query line passes through a point known in advance for pr eprocessing we present an algorithm with O(n log n) preprocessing time and space to answer the closest point query in O(log(2) n) time. (C) 1998 Elsevier Science B.V. All rights reserved.