Approximating center points with iterated radon points
Approximating center points with iterated radon points
复制标题
用迭代氡点近似中心点
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
S. Teng
中科院分区：
文献类型：
--
作者：
K. Clarkson;D. Eppstein;G. Miller;Carl Sturtivant;S. Teng
We describe a practical and provably good algorithm forapproximating center points in any number of dimensions. Here<?Pub Fmt italic>c<?Pub Fmt /italic> is a center point of a point set<?Pub Fmt italic>P<?Pub Fmt /italic> in <inline-equation><f><blkbd>R</blkbd><sup>d</sup></f></inline-equation> if every closed halfspace containing<?Pub Fmt italic>c<?Pub Fmt /italic> contains at least <inline-equation><f><fen lp="vb">P<rp post="vb"></fen>/<fen lp="par">d+1<rp post="par"></fen></f></inline-equation> points of <?Pub Fmt italic>P<?Pub Fmt /italic>. Ouralgorithm has a small constant factor and is the first approximatecenter point algorithm whose complexity is subexponential in<?Pub Fmt italic>d<?Pub Fmt /italic>. Moreover, it can be optimallyparallelized to require <inline-equation><f>O<fen lp="par"><lim align="r"><op><rf>log</rf></op><ul>2</ul></lim>d<rf>log</rf><rf>log</rf>n<rp post="par"></fen></f></inline-equation> <?Pub Caret>time. Our algorithm has been used in meshpartitioning methods, and has the potential to improve results inpractice for constructing weak ε-nets and other geometricalgorithms. We derive a variant of our algorithm with a time bound fullypolynomial in <?Pub Fmt italic>d<?Pub Fmt /italic>, and show how tocombine our approach with previous techniques to compute high qualitycenter points more quickly.
