Approximation and exact algorithms for minimum-width annuli and shells

Pankaj K. Agarwal; Boris Aronov; Sariel Har-Peled; Micha Sharir

doi:10.1145/304893.304992

Approximation and exact algorithms for minimum-width annuli and shells

Pankaj K. Agarwal, Boris Aronov, Sariel Har-Peled, Micha Sharir

Research output: Contribution to conference › Paper › peer-review

Abstract

The approximation and the exact algorithms to compute the minimum-width shell or annulus are discussed. To measure the S or the roundness of a set of n points in R^d, the S can be approximated with a sphere (Γ) so that the maximum distance between a point of S and Γ is minimized. It was found that the problem of measuring the roundness of S is equivalent to computing a shell of the smallest width that contains S.

Original language	English (US)
Pages	380-389
Number of pages	10
DOIs	https://doi.org/10.1145/304893.304992
State	Published - 1999
Externally published	Yes
Event	Proceedings of the 1999 15th Annual Symposium on Computational Geometry - Miami Beach, FL, USA Duration: Jun 13 1999 → Jun 16 1999

Conference

Conference	Proceedings of the 1999 15th Annual Symposium on Computational Geometry
City	Miami Beach, FL, USA
Period	6/13/99 → 6/16/99

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Online availability

10.1145/304893.304992

Library availability

Discover UIUC Full Text

Cite this

@conference{cfacdeabb97141c3ad161e291ce16fbb,

title = "Approximation and exact algorithms for minimum-width annuli and shells",

abstract = "The approximation and the exact algorithms to compute the minimum-width shell or annulus are discussed. To measure the S or the roundness of a set of n points in Rd, the S can be approximated with a sphere (Γ) so that the maximum distance between a point of S and Γ is minimized. It was found that the problem of measuring the roundness of S is equivalent to computing a shell of the smallest width that contains S.",

author = "Agarwal, {Pankaj K.} and Boris Aronov and Sariel Har-Peled and Micha Sharir",

year = "1999",

doi = "10.1145/304893.304992",

language = "English (US)",

pages = "380--389",

note = "Proceedings of the 1999 15th Annual Symposium on Computational Geometry ; Conference date: 13-06-1999 Through 16-06-1999",

}

TY - CONF

T1 - Approximation and exact algorithms for minimum-width annuli and shells

AU - Agarwal, Pankaj K.

AU - Aronov, Boris

AU - Har-Peled, Sariel

AU - Sharir, Micha

PY - 1999

Y1 - 1999

N2 - The approximation and the exact algorithms to compute the minimum-width shell or annulus are discussed. To measure the S or the roundness of a set of n points in Rd, the S can be approximated with a sphere (Γ) so that the maximum distance between a point of S and Γ is minimized. It was found that the problem of measuring the roundness of S is equivalent to computing a shell of the smallest width that contains S.

AB - The approximation and the exact algorithms to compute the minimum-width shell or annulus are discussed. To measure the S or the roundness of a set of n points in Rd, the S can be approximated with a sphere (Γ) so that the maximum distance between a point of S and Γ is minimized. It was found that the problem of measuring the roundness of S is equivalent to computing a shell of the smallest width that contains S.

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

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

U2 - 10.1145/304893.304992

DO - 10.1145/304893.304992

M3 - Paper

AN - SCOPUS:0032650948

SP - 380

EP - 389

T2 - Proceedings of the 1999 15th Annual Symposium on Computational Geometry

Y2 - 13 June 1999 through 16 June 1999

ER -

Approximation and exact algorithms for minimum-width annuli and shells

Abstract

Conference

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this