Efficient Approximation Algorithm with Partition Technique for the Diameter of A Set of Points in 2D Plane

Zhipeng Wang; Jieying Hong; Wei Niu

doi:10.1088/1742-6596/1087/2/022035

Efficient Approximation Algorithm with Partition Technique for the Diameter of A Set of Points in 2D Plane

Zhipeng Wang^*
, Jieying Hong
, Wei Niu

^*Corresponding author for this work

Sino-French Engineer School/School of General Engineering

Beihang University
ESSEC Business School

Research output: Contribution to journal › Conference article › peer-review

Abstract

We apply the partition technique to build an efficient approximation algorithm to compute the diameter of a set of points in 2D Euclidean plane. The optimal time of our algorithm is O(N + (1/δ)log(1/δ)), up to a (1 + δ) factor, for 2-dimensional N-point set. The error bounds are proved strictly. Compared to the prior works, our algorithm is without complex data structure and easy to be implanted. The partition technique is general and may be applied in higher-dimensional space.

Original language	English
Article number	022035
Journal	Journal of Physics: Conference Series
Volume	1087
Issue number	2
DOIs	https://doi.org/10.1088/1742-6596/1087/2/022035
State	Published - 2 Oct 2018
Event	1st International Conference on Advanced Algorithms and Control Engineering, ICAACE 2018 - Pingtung, Taiwan, Province of China Duration: 10 Aug 2018 → 12 Aug 2018

Access to Document

10.1088/1742-6596/1087/2/022035

Cite this

@article{13e67ef7c7c24d7fa43b3be490698f08,

title = "Efficient Approximation Algorithm with Partition Technique for the Diameter of A Set of Points in 2D Plane",

abstract = "We apply the partition technique to build an efficient approximation algorithm to compute the diameter of a set of points in 2D Euclidean plane. The optimal time of our algorithm is O(N + (1/δ)log(1/δ)), up to a (1 + δ) factor, for 2-dimensional N-point set. The error bounds are proved strictly. Compared to the prior works, our algorithm is without complex data structure and easy to be implanted. The partition technique is general and may be applied in higher-dimensional space.",

author = "Zhipeng Wang and Jieying Hong and Wei Niu",

note = "Publisher Copyright: {\textcopyright} Published under licence by IOP Publishing Ltd.; 1st International Conference on Advanced Algorithms and Control Engineering, ICAACE 2018 ; Conference date: 10-08-2018 Through 12-08-2018",

year = "2018",

month = oct,

day = "2",

doi = "10.1088/1742-6596/1087/2/022035",

language = "英语",

volume = "1087",

journal = "Journal of Physics: Conference Series",

issn = "1742-6588",

publisher = "IOP Publishing Ltd.",

number = "2",

}

TY - JOUR

T1 - Efficient Approximation Algorithm with Partition Technique for the Diameter of A Set of Points in 2D Plane

AU - Wang, Zhipeng

AU - Hong, Jieying

AU - Niu, Wei

N1 - Publisher Copyright: © Published under licence by IOP Publishing Ltd.

PY - 2018/10/2

Y1 - 2018/10/2

N2 - We apply the partition technique to build an efficient approximation algorithm to compute the diameter of a set of points in 2D Euclidean plane. The optimal time of our algorithm is O(N + (1/δ)log(1/δ)), up to a (1 + δ) factor, for 2-dimensional N-point set. The error bounds are proved strictly. Compared to the prior works, our algorithm is without complex data structure and easy to be implanted. The partition technique is general and may be applied in higher-dimensional space.

AB - We apply the partition technique to build an efficient approximation algorithm to compute the diameter of a set of points in 2D Euclidean plane. The optimal time of our algorithm is O(N + (1/δ)log(1/δ)), up to a (1 + δ) factor, for 2-dimensional N-point set. The error bounds are proved strictly. Compared to the prior works, our algorithm is without complex data structure and easy to be implanted. The partition technique is general and may be applied in higher-dimensional space.

UR - https://www.scopus.com/pages/publications/85054905251

U2 - 10.1088/1742-6596/1087/2/022035

DO - 10.1088/1742-6596/1087/2/022035

M3 - 会议文章

AN - SCOPUS:85054905251

SN - 1742-6588

VL - 1087

JO - Journal of Physics: Conference Series

JF - Journal of Physics: Conference Series

IS - 2

M1 - 022035

T2 - 1st International Conference on Advanced Algorithms and Control Engineering, ICAACE 2018

Y2 - 10 August 2018 through 12 August 2018

ER -

Efficient Approximation Algorithm with Partition Technique for the Diameter of A Set of Points in 2D Plane

Abstract

Access to Document

Other files and links

Fingerprint

Cite this