### Abstract

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

Original language | English (US) |
---|---|

Pages (from-to) | 205-211 |

Number of pages | 7 |

Journal | Information Processing Letters |

Volume | 32 |

Issue number | 4 |

DOIs | |

State | Published - Sep 1 1989 |

### Fingerprint

### 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

*Information Processing Letters*,

*32*(4), 205-211. https://doi.org/10.1016/0020-0190(89)90045-8

}

*Information Processing Letters*, vol. 32, no. 4, pp. 205-211. https://doi.org/10.1016/0020-0190(89)90045-8

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

Research output: Contribution to journal › Article

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 -