Computing a segment center for a planar point set


Journal Article

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. © 1993 Academic Press, Inc.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Efrat, A; Sharir, M; Toledo, S

Published Date

  • January 1, 1993

Published In

Volume / Issue

  • 15 / 2

Start / End Page

  • 314 - 323

International Standard Serial Number (ISSN)

  • 0196-6774

Digital Object Identifier (DOI)

  • 10.1006/jagm.1993.1043

Citation Source

  • Scopus