Zobrazeno 1 - 10
of 339
pro vyhledávání: '"ARYA, SUNIL"'
Approximating convex bodies is a fundamental question in geometry and has a wide variety of applications. Given a convex body $K$ of diameter $\Delta$ in $\mathbb{R}^d$ for fixed $d$, the objective is to minimize the number of vertices (alternatively
Externí odkaz:
http://arxiv.org/abs/2306.15648
We present a new approach to approximate nearest-neighbor queries in fixed dimension under a variety of non-Euclidean distances. We are given a set $S$ of $n$ points in $\mathbb{R}^d$, an approximation parameter $\varepsilon > 0$, and a distance func
Externí odkaz:
http://arxiv.org/abs/2306.15621
Autor:
Arya, Sunil, Mount, David M.
Approximating convex bodies is a fundamental question in geometry and has a wide variety of applications. Consider a convex body $K$ of diameter $\Delta$ in $\textbf{R}^d$ for fixed $d$. The objective is to minimize the number of vertices (alternativ
Externí odkaz:
http://arxiv.org/abs/2303.09586
Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body $K$ and $\epsilon> 0$, a covering is a collection of convex bodies
Externí odkaz:
http://arxiv.org/abs/2303.08349
Publikováno v:
SODA 2020, 786-805, 2020
This paper considers the question of how to succinctly approximate a multidimensional convex body by a polytope. Given a convex body $K$ of unit diameter in Euclidean $d$-dimensional space (where $d$ is a constant) and an error parameter $\varepsilon
Externí odkaz:
http://arxiv.org/abs/1910.14459
Publikováno v:
ESA 2018
Approximation problems involving a single convex body in $d$-dimensional space have received a great deal of attention in the computational geometry community. In contrast, works involving multiple convex bodies are generally limited to dimensions $d
Externí odkaz:
http://arxiv.org/abs/1807.00484
Publikováno v:
Proc. 33rd International Symposium on Computational Geometry (SoCG 2017), pages 10:1-15, 2017
The computation of (i) $\varepsilon$-kernels, (ii) approximate diameter, and (iii) approximate bichromatic closest pair are fundamental problems in geometric approximation. In this paper, we describe new algorithms that offer significant improvements
Externí odkaz:
http://arxiv.org/abs/1703.10868
In the polytope membership problem, a convex polytope $K$ in $R^d$ is given, and the objective is to preprocess $K$ into a data structure so that, given a query point $q \in R^d$, it is possible to determine efficiently whether $q \in K$. We consider
Externí odkaz:
http://arxiv.org/abs/1612.01696
Publikováno v:
SIAM J. Comput., 47(1), 1-51, 2018
In the polytope membership problem, a convex polytope $K$ in $\mathbb{R}^d$ is given, and the objective is to preprocess $K$ into a data structure so that, given any query point $q \in \mathbb{R}^d$, it is possible to determine efficiently whether $q
Externí odkaz:
http://arxiv.org/abs/1604.01183
Publikováno v:
Discrete & Computational Geometry, Volume 58, Issue 4, pp 849-870, 2017
Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body $K$ of diameter $\mathrm{diam}(K)$ is given in Euclidean $d$-dimensional space, where $d$ is a constant. Given an error parameter
Externí odkaz:
http://arxiv.org/abs/1604.01175