Name
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]. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1137856.1137861 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
open problem,interior point o,core-set concept,n d-dimensional halfspaces,high dimensional polytope,algorithm compute,maximum inscribed sphere,bounded aspect ratio,aspect-ratio-bounded polytope,efficient algorithm,interior point,polytope,approximation,chebyshev center | Discrete mathematics,Combinatorics,Open problem,Algorithm,Chebyshev center,Polytope,e,Inscribed sphere,Interior point method,Mathematics,Special case,Bounded function | Conference |
ISBN | Citations | PageRank |
1-59593-340-9 | 2 | 0.41 |
References | Authors | |
13 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yulai Xie | 1 | 54 | 9.67 |
| Jack Snoeyink | 2 | 2842 | 231.68 |
| Jinhui Xu | 3 | 665 | 78.86 |