Fast algorithms for computing the diameter of a finite planar set

Binay K. Bhattacharya; Godfried T. Toussaint

doi:10.1007/BF01901195

Fast algorithms for computing the diameter of a finite planar set

Binay K. Bhattacharya, Godfried T. Toussaint

Computer Science

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

Abstract

Three algorithms for computing the diameter of a finite planar set are proposed. Although all three algorithms have (O(n²) worst-case running time, an expected-complexity analysis shows that, under reasonable probabilistic assumptions, all three algorithms have linear expected running time. Experimental results indicate that two of these algorithms perform very well for some distributions, and are competitive with an existing method. Finally, we exhibit situations where these exact algorithms out-perform a published approximate algorithm.

Original language	English (US)
Pages (from-to)	379-388
Number of pages	10
Journal	The Visual Computer
Volume	3
Issue number	6
DOIs	https://doi.org/10.1007/BF01901195
State	Published - Nov 1988

Keywords

Approximate algorithm
Diameter
Expected complexity
Monte Carlo simulation

ASJC Scopus subject areas

Software
Computer Vision and Pattern Recognition
Computer Graphics and Computer-Aided Design

Access to Document

10.1007/BF01901195

Cite this

@article{17234352af9c4ffaa146cc0961740fe4,

title = "Fast algorithms for computing the diameter of a finite planar set",

abstract = "Three algorithms for computing the diameter of a finite planar set are proposed. Although all three algorithms have (O(n2) worst-case running time, an expected-complexity analysis shows that, under reasonable probabilistic assumptions, all three algorithms have linear expected running time. Experimental results indicate that two of these algorithms perform very well for some distributions, and are competitive with an existing method. Finally, we exhibit situations where these exact algorithms out-perform a published approximate algorithm.",

keywords = "Approximate algorithm, Diameter, Expected complexity, Monte Carlo simulation",

author = "Bhattacharya, {Binay K.} and Toussaint, {Godfried T.}",

year = "1988",

month = nov,

doi = "10.1007/BF01901195",

language = "English (US)",

volume = "3",

pages = "379--388",

journal = "The Visual Computer",

issn = "0178-2789",

publisher = "Springer Verlag",

number = "6",

}

TY - JOUR

T1 - Fast algorithms for computing the diameter of a finite planar set

AU - Bhattacharya, Binay K.

AU - Toussaint, Godfried T.

PY - 1988/11

Y1 - 1988/11

N2 - Three algorithms for computing the diameter of a finite planar set are proposed. Although all three algorithms have (O(n2) worst-case running time, an expected-complexity analysis shows that, under reasonable probabilistic assumptions, all three algorithms have linear expected running time. Experimental results indicate that two of these algorithms perform very well for some distributions, and are competitive with an existing method. Finally, we exhibit situations where these exact algorithms out-perform a published approximate algorithm.

AB - Three algorithms for computing the diameter of a finite planar set are proposed. Although all three algorithms have (O(n2) worst-case running time, an expected-complexity analysis shows that, under reasonable probabilistic assumptions, all three algorithms have linear expected running time. Experimental results indicate that two of these algorithms perform very well for some distributions, and are competitive with an existing method. Finally, we exhibit situations where these exact algorithms out-perform a published approximate algorithm.

KW - Approximate algorithm

KW - Diameter

KW - Expected complexity

KW - Monte Carlo simulation

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

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

U2 - 10.1007/BF01901195

DO - 10.1007/BF01901195

M3 - Article

AN - SCOPUS:34250096962

SN - 0178-2789

VL - 3

SP - 379

EP - 388

JO - The Visual Computer

JF - The Visual Computer

IS - 6

ER -

Fast algorithms for computing the diameter of a finite planar set

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this