A near-linear algorithm for the planar segment-center problem

A. Efrat; M. Sharir

doi:10.1007/BF02711511

A near-linear algorithm for the planar segment-center problem

A. Efrat, M. Sharir

Research output: Contribution to journal › Article › peer-review

20 Scopus citations

Abstract

Let P be a set of n points in the plane and let e be a segment of fixed length. The segment-center problem is to find a placement of e (allowing translation and rotation) which minimizes the maximum euclidean distance from e to the points of P. We present an algorithm that solves the problem in time O(n^1+ε), for any ε > 0, improving the previous solution of Agarwal et al. [3] by nearly a factor of O(n).

Original language	English (US)
Pages (from-to)	239-257
Number of pages	19
Journal	Discrete and Computational Geometry
Volume	16
Issue number	3
DOIs	https://doi.org/10.1007/BF02711511
State	Published - Oct 1996
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/BF02711511

Cite this

@article{47823af8ce1c4a3b97385b1b0568e0a0,

title = "A near-linear algorithm for the planar segment-center problem",

abstract = "Let P be a set of n points in the plane and let e be a segment of fixed length. The segment-center problem is to find a placement of e (allowing translation and rotation) which minimizes the maximum euclidean distance from e to the points of P. We present an algorithm that solves the problem in time O(n1+ε), for any ε > 0, improving the previous solution of Agarwal et al. [3] by nearly a factor of O(n).",

author = "A. Efrat and M. Sharir",

year = "1996",

month = oct,

doi = "10.1007/BF02711511",

language = "English (US)",

volume = "16",

pages = "239--257",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - A near-linear algorithm for the planar segment-center problem

AU - Efrat, A.

AU - Sharir, M.

PY - 1996/10

Y1 - 1996/10

N2 - Let P be a set of n points in the plane and let e be a segment of fixed length. The segment-center problem is to find a placement of e (allowing translation and rotation) which minimizes the maximum euclidean distance from e to the points of P. We present an algorithm that solves the problem in time O(n1+ε), for any ε > 0, improving the previous solution of Agarwal et al. [3] by nearly a factor of O(n).

AB - Let P be a set of n points in the plane and let e be a segment of fixed length. The segment-center problem is to find a placement of e (allowing translation and rotation) which minimizes the maximum euclidean distance from e to the points of P. We present an algorithm that solves the problem in time O(n1+ε), for any ε > 0, improving the previous solution of Agarwal et al. [3] by nearly a factor of O(n).

UR - http://www.scopus.com/inward/record.url?scp=0030492048&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030492048&partnerID=8YFLogxK

U2 - 10.1007/BF02711511

DO - 10.1007/BF02711511

M3 - Article

AN - SCOPUS:0030492048

SN - 0179-5376

VL - 16

SP - 239

EP - 257

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 3

ER -

A near-linear algorithm for the planar segment-center problem

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this