Computing a segment center for a planar point set

Pankaj K. Agarwal; Alon Efrat; Micha Sharir; Sivan Toledo

doi:10.1006/jagm.1993.1043

Computing a segment center for a planar point set

Pankaj K. Agarwal, Alon Efrat, Micha Sharir, Sivan Toledo

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

16 Scopus citations

Abstract

Given a set S of n points in the plane and a segment e, a center placement of e is a placement (allowing translation and rotation) that minimizes the maximum distance from e to the points of S. We present an algorithm for computing a center placement for S, whose running time is O(n²α(n)log³n), where α(n) is the inverse Ackermann function. The algorithm makes use of the parametric searching technique of Megiddo.

Original language	English (US)
Pages (from-to)	314-323
Number of pages	10
Journal	Journal of Algorithms
Volume	15
Issue number	2
DOIs	https://doi.org/10.1006/jagm.1993.1043
State	Published - Sep 1993
Externally published	Yes

ASJC Scopus subject areas

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1006/jagm.1993.1043

Cite this

@article{454f015173cc43809b9e055efa5d0a4a,

title = "Computing a segment center for a planar point set",

abstract = "Given a set S of n points in the plane and a segment e, a center placement of e is a placement (allowing translation and rotation) that minimizes the maximum distance from e to the points of S. We present an algorithm for computing a center placement for S, whose running time is O(n2α(n)log3n), where α(n) is the inverse Ackermann function. The algorithm makes use of the parametric searching technique of Megiddo.",

author = "Agarwal, {Pankaj K.} and Alon Efrat and Micha Sharir and Sivan Toledo",

year = "1993",

month = sep,

doi = "10.1006/jagm.1993.1043",

language = "English (US)",

volume = "15",

pages = "314--323",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Computing a segment center for a planar point set

AU - Agarwal, Pankaj K.

AU - Efrat, Alon

AU - Sharir, Micha

AU - Toledo, Sivan

PY - 1993/9

Y1 - 1993/9

N2 - Given a set S of n points in the plane and a segment e, a center placement of e is a placement (allowing translation and rotation) that minimizes the maximum distance from e to the points of S. We present an algorithm for computing a center placement for S, whose running time is O(n2α(n)log3n), where α(n) is the inverse Ackermann function. The algorithm makes use of the parametric searching technique of Megiddo.

AB - Given a set S of n points in the plane and a segment e, a center placement of e is a placement (allowing translation and rotation) that minimizes the maximum distance from e to the points of S. We present an algorithm for computing a center placement for S, whose running time is O(n2α(n)log3n), where α(n) is the inverse Ackermann function. The algorithm makes use of the parametric searching technique of Megiddo.

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

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

U2 - 10.1006/jagm.1993.1043

DO - 10.1006/jagm.1993.1043

M3 - Article

AN - SCOPUS:0001078023

SN - 0196-6774

VL - 15

SP - 314

EP - 323

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 2

ER -

Computing a segment center for a planar point set

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this