Approximating the diameter of a set of points in the Euclidean space

Ömer Eg̃eciog̃lu, Bahman Kalantari

Research output: Contribution to journalArticle

18 Citations (Scopus)

Abstract

Given a set P with n points in Rk, its diameter dp is the maximum of the Euclidean distances between its points. We describe an algorithm that in m≤n iterations obtains r1<r2<⋯<rm≤dp≤min{ 3r1, 5-2 3rm}. For k fixed, the cost of each iteration is O(n). In particular, the first approximation r1 is within 3 of dp, independent of the dimension k.

Original languageEnglish (US)
Pages (from-to)205-211
Number of pages7
JournalInformation Processing Letters
Volume32
Issue number4
DOIs
StatePublished - Sep 1 1989

Fingerprint

Diameter of a set
Set of points
Euclidean space
Iteration
Euclidean Distance
Costs
Approximation

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Computational geometry
  • approximation algorithm
  • diameter computation

Cite this

@article{3e2663e6b4ed49c78922e69e92663e42,
title = "Approximating the diameter of a set of points in the Euclidean space",
abstract = "Given a set P with n points in Rk, its diameter dp is the maximum of the Euclidean distances between its points. We describe an algorithm that in m≤n iterations obtains r12<⋯m≤dp≤min{ 3r1, 5-2 3rm}. For k fixed, the cost of each iteration is O(n). In particular, the first approximation r1 is within 3 of dp, independent of the dimension k.",
keywords = "Computational geometry, approximation algorithm, diameter computation",
author = "{\"O}mer Eg̃eciog̃lu and Bahman Kalantari",
year = "1989",
month = "9",
day = "1",
doi = "10.1016/0020-0190(89)90045-8",
language = "English (US)",
volume = "32",
pages = "205--211",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "4",

}

Approximating the diameter of a set of points in the Euclidean space. / Eg̃eciog̃lu, Ömer; Kalantari, Bahman.

In: Information Processing Letters, Vol. 32, No. 4, 01.09.1989, p. 205-211.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Approximating the diameter of a set of points in the Euclidean space

AU - Eg̃eciog̃lu, Ömer

AU - Kalantari, Bahman

PY - 1989/9/1

Y1 - 1989/9/1

N2 - Given a set P with n points in Rk, its diameter dp is the maximum of the Euclidean distances between its points. We describe an algorithm that in m≤n iterations obtains r12<⋯m≤dp≤min{ 3r1, 5-2 3rm}. For k fixed, the cost of each iteration is O(n). In particular, the first approximation r1 is within 3 of dp, independent of the dimension k.

AB - Given a set P with n points in Rk, its diameter dp is the maximum of the Euclidean distances between its points. We describe an algorithm that in m≤n iterations obtains r12<⋯m≤dp≤min{ 3r1, 5-2 3rm}. For k fixed, the cost of each iteration is O(n). In particular, the first approximation r1 is within 3 of dp, independent of the dimension k.

KW - Computational geometry

KW - approximation algorithm

KW - diameter computation

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

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

U2 - 10.1016/0020-0190(89)90045-8

DO - 10.1016/0020-0190(89)90045-8

M3 - Article

AN - SCOPUS:0024737466

VL - 32

SP - 205

EP - 211

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 4

ER -