A NEAR-LINEAR ALGORITHM FOR THE PLANAR SEGMENT-CENTER PROBLEM

Authors
EFRAT A SHARIR M
Citation
A. Efrat et M. Sharir, A NEAR-LINEAR ALGORITHM FOR THE PLANAR SEGMENT-CENTER PROBLEM, Discrete & computational geometry, 16(3), 1996, pp. 239-257
Citations number
27
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, General","Computer Science Theory & Methods",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
16
Issue
3
Year of publication
1996
Pages
239 - 257
Database
ISI
SICI code
0179-5376(1996)16:3<239:ANAFTP>2.0.ZU;2-S
Abstract
Let P be a set of n points in the plane and let e be a segment of fixe d length. The segment-center problem is to find a placement of e (allo wing translation and rotation) which minimizes the maximum euclidean d istance from e to the points of P. We present an algorithm that solves the problem in time O(n(l+E)), for any epsilon >0, improving the prev ious solution of Agarwal et al. [3] by nearly a factor of O(n).