Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope

Yulai Xie; Jack Snoeyink; Jinhui Xu

doi:10.1145/1137856.1137861

Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope

Yulai Xie
, Jack Snoeyink
, Jinhui Xu

Department of Computer Science and Engineering

SUNY Buffalo
University of North Carolina at Chapel Hill

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

Abstract

In this paper, we consider the problem of computing a maximum inscribed sphere inside a high dimensional polytope formed by a set of halfspaces (or linear constraints) and with bounded aspect ratio, and present an efficient algorithm for computing a (1 - ε)-approximation of the sphere. More specifically, given any aspect-ratio-bounded polytope P defined by n d-dimensional halfspaces, an interior point O of P, and a constant ε > 0, our algorithm computes in O(nd/ε³) time a sphere inside P with a radius no less than (1 - ε)R_opt, where R_opt is the radius of a maximum inscribed sphere of P. Our algorithm is based on the core-set concept and a number of interesting geometric observations. Our result solves a special case of an open problem posted by Khachiyan and Todd [13].

Original language	English
Title of host publication	Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
Publisher	Association for Computing Machinery (ACM)
Pages	21-29
Number of pages	9
ISBN (Print)	1595933409, 9781595933409
DOIs	https://doi.org/10.1145/1137856.1137861
State	Published - 2006
Event	22nd Annual Symposium on Computational Geometry 2006, SCG'06 - Sedona, AZ, United States Duration: Jun 5 2006 → Jun 7 2006

Publication series

Name	Proceedings of the Annual Symposium on Computational Geometry
Volume	2006

Conference

Conference	22nd Annual Symposium on Computational Geometry 2006, SCG'06
Country/Territory	United States
City	Sedona, AZ
Period	06/5/06 → 06/7/06

Keywords

Approximation
Chebyshev Center
Core-Set
Maximum Inscribed Sphere
Polytope

Access to Document

10.1145/1137856.1137861

Cite this

Xie, Y., Snoeyink, J., & Xu, J. (2006). Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope. In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06 (pp. 21-29). (Proceedings of the Annual Symposium on Computational Geometry; Vol. 2006). Association for Computing Machinery (ACM). https://doi.org/10.1145/1137856.1137861

@inproceedings{76af02377a1a468fa4951aa2484a3586,

title = "Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope",

abstract = "In this paper, we consider the problem of computing a maximum inscribed sphere inside a high dimensional polytope formed by a set of halfspaces (or linear constraints) and with bounded aspect ratio, and present an efficient algorithm for computing a (1 - ε)-approximation of the sphere. More specifically, given any aspect-ratio-bounded polytope P defined by n d-dimensional halfspaces, an interior point O of P, and a constant ε > 0, our algorithm computes in O(nd/ε3) time a sphere inside P with a radius no less than (1 - ε)Ropt, where Ropt is the radius of a maximum inscribed sphere of P. Our algorithm is based on the core-set concept and a number of interesting geometric observations. Our result solves a special case of an open problem posted by Khachiyan and Todd [13].",

keywords = "Approximation, Chebyshev Center, Core-Set, Maximum Inscribed Sphere, Polytope",

author = "Yulai Xie and Jack Snoeyink and Jinhui Xu",

year = "2006",

doi = "10.1145/1137856.1137861",

language = "English",

isbn = "1595933409",

series = "Proceedings of the Annual Symposium on Computational Geometry",

publisher = "Association for Computing Machinery (ACM)",

pages = "21--29",

booktitle = "Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06",

note = "22nd Annual Symposium on Computational Geometry 2006, SCG'06 ; Conference date: 05-06-2006 Through 07-06-2006",

}

Xie, Y, Snoeyink, J & Xu, J 2006, Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope. in Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06. Proceedings of the Annual Symposium on Computational Geometry, vol. 2006, Association for Computing Machinery (ACM), pp. 21-29, 22nd Annual Symposium on Computational Geometry 2006, SCG'06, Sedona, AZ, United States, 06/5/06. https://doi.org/10.1145/1137856.1137861

Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope. / Xie, Yulai; Snoeyink, Jack; Xu, Jinhui.
Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06. Association for Computing Machinery (ACM), 2006. p. 21-29 (Proceedings of the Annual Symposium on Computational Geometry; Vol. 2006).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope

AU - Xie, Yulai

AU - Snoeyink, Jack

AU - Xu, Jinhui

PY - 2006

Y1 - 2006

N2 - In this paper, we consider the problem of computing a maximum inscribed sphere inside a high dimensional polytope formed by a set of halfspaces (or linear constraints) and with bounded aspect ratio, and present an efficient algorithm for computing a (1 - ε)-approximation of the sphere. More specifically, given any aspect-ratio-bounded polytope P defined by n d-dimensional halfspaces, an interior point O of P, and a constant ε > 0, our algorithm computes in O(nd/ε3) time a sphere inside P with a radius no less than (1 - ε)Ropt, where Ropt is the radius of a maximum inscribed sphere of P. Our algorithm is based on the core-set concept and a number of interesting geometric observations. Our result solves a special case of an open problem posted by Khachiyan and Todd [13].

AB - In this paper, we consider the problem of computing a maximum inscribed sphere inside a high dimensional polytope formed by a set of halfspaces (or linear constraints) and with bounded aspect ratio, and present an efficient algorithm for computing a (1 - ε)-approximation of the sphere. More specifically, given any aspect-ratio-bounded polytope P defined by n d-dimensional halfspaces, an interior point O of P, and a constant ε > 0, our algorithm computes in O(nd/ε3) time a sphere inside P with a radius no less than (1 - ε)Ropt, where Ropt is the radius of a maximum inscribed sphere of P. Our algorithm is based on the core-set concept and a number of interesting geometric observations. Our result solves a special case of an open problem posted by Khachiyan and Todd [13].

KW - Approximation

KW - Chebyshev Center

KW - Core-Set

KW - Maximum Inscribed Sphere

KW - Polytope

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

U2 - 10.1145/1137856.1137861

DO - 10.1145/1137856.1137861

M3 - Conference contribution

AN - SCOPUS:33748058834

SN - 1595933409

SN - 9781595933409

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 21

EP - 29

BT - Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06

PB - Association for Computing Machinery (ACM)

T2 - 22nd Annual Symposium on Computational Geometry 2006, SCG'06

Y2 - 5 June 2006 through 7 June 2006

ER -

Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this