Computing a segment center for a planar point set

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

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)314-323
Number of pages10
JournalJournal of Algorithms
Issue number2
StatePublished - Sep 1993

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'Computing a segment center for a planar point set'. Together they form a unique fingerprint.

Cite this