ACAruni Choudhary
Aruni Choudhary
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Aruni Choudhary has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Michael Kerber
Graz University of Technology, Graz, Austria
3 shared publications - Sharath Raghvendra
Department of Computer Science Virginia Tech
3 shared publications - Arijit Ghosh
Indian Statistical Institute, Kolkata, India
1 shared publication - Mathijs Wintraecken
Centre Inria d’Université Côte d’Azur, Université Côte d’Azur, Inria, Valbonne, France
1 shared publication - Siargey Kachanovich
Corpy&Co., Inc., Tokyo, Japan
1 shared publication - Wolfgang Mulzer
Institut für Informatik, Freie Universität Berlin, Berlin, Germany
1 shared publication
Latest Publications
- Open Access
- 12 April 2022
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 68 (4) , 964-996
No-Dimensional Tverberg Theorems and Algorithms
Tverberg’s theorem states that for any $$k\ge 2$$ and any set $$P\subset {\mathbb {R}}^d$$ of at least $$(d+1)(k-1)+1$$ points in d dimensions, we can partition P into k subsets whose convex hulls have a non-empty intersection. The associated search problem of finding the partition lies in the complexity class $$\text {CLS} = \text {PPAD} \cap \text {PLS}$$ , but no hardness results are known. In the colorful Tverberg theorem, the points in P have colors, and under certain conditions, P can be partitioned into colorful sets, in which each color appears exactly once and whose convex hulls intersect. To date, the complexity of the associated search problem is unresolved. Recently, Adiprasito, Bárány, and Mustafa (SODA 2019) gave a no-dimensional Tverberg theorem, in which the convex hulls may intersect in an approximate fashion. This relaxes the requirement on the cardinality of P. The argument is constructive, but does not result in a polynomial-time algorithm. We present a deterministic algorithm that finds for any n-point set $$P\subset {\mathbb {R}}^d$$ and any $$k\in \{2,\dots ,n\}$$ in $$O(nd\lceil {\log k}\rceil )$$ time a k-partition of P such that there is a ball of radius $$O((k/\sqrt{n}){\text {diam}}(P))$$ that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, our result provides a remarkably efficient and simple new notion of approximation. Our main contribution is to generalize Sarkaria’s method (Israel Journal Math., 1992) to reduce the Tverberg problem to the colorful Carathéodory problem (in the simplified tensor product interpretation of Bárány and Onn) and to apply it algorithmically. It turns out that this not only leads to an alternative algorithmic proof of a no-dimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem.- 12 April 2022
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 68 (4) , 964-996
Open AccessNo-Dimensional Tverberg Theorems and Algorithms
Tverberg’s theorem states that for any $$k\ge 2$$ and any set $$P\subset {\mathbb {R}}^d$$ of at least $$(d+1)(k-1)+1$$ points in d dimensions, we can partition P into k subsets whose convex hulls have a non-empty intersection. The associated search problem of finding the partition lies in the complexity class $$\text {CLS} = \text {PPAD} \cap \text {PLS}$$ , but no hardness results are known. In the colorful Tverberg theorem, the points in P have colors, and under certain conditions, P can be partitioned into colorful sets, in which each color appears exactly once and whose convex hulls intersect. To date, the complexity of the associated search problem is unresolved. Recently, Adiprasito, Bárány, and Mustafa (SODA 2019) gave a no-dimensional Tverberg theorem, in which the convex hulls may intersect in an approximate fashion. This relaxes the requirement on the cardinality of P. The argument is constructive, but does not result in a polynomial-time algorithm. We present a deterministic algorithm that finds for any n-point set $$P\subset {\mathbb {R}}^d$$ and any $$k\in \{2,\dots ,n\}$$ in $$O(nd\lceil {\log k}\rceil )$$ time a k-partition of P such that there is a ball of radius $$O((k/\sqrt{n}){\text {diam}}(P))$$ that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, our result provides a remarkably efficient and simple new notion of approximation. Our main contribution is to generalize Sarkaria’s method (Israel Journal Math., 1992) to reduce the Tverberg problem to the colorful Carathéodory problem (in the simplified tensor product interpretation of Bárány and Onn) and to apply it algorithmically. It turns out that this not only leads to an alternative algorithmic proof of a no-dimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem. - Open Access
- 15 May 2021
- Published by Springer Nature in Journal of Applied and Computational Topology
- Vol. 5 (3) , 425-458
Improved approximate rips filtrations with shifted integer lattices and cubical complexes
Rips complexes are important structures for analyzing topological features of metric spaces. Unfortunately, generating these complexes is expensive because of a combinatorial explosion in the complex size. Fornpoints in $$\mathbb {R}^d$$ , we present a scheme to construct a 2-approximation of the filtration of the Rips complex in the $$L_\infty $$ -norm, which extends to a $$2d^{0.25}$$ -approximation in the Euclidean case. Thek-skeleton of the resulting approximation has a total size of $$n2^{O(d\log k +d)}$$ . The scheme is based on the integer lattice and simplicial complexes based on the barycentric subdivision of thed-cube. We extend our result to use cubical complexes in place of simplicial complexes by introducingcubical mapsbetween complexes. We get the same approximation guarantee as the simplicial case, while reducing the total size of the approximation to only $$n2^{O(d)}$$ (cubical) cells. There are two novel techniques that we use in this paper. The first is the use ofacyclic carriersfor proving our approximation result. In our application, these are maps which relate the Rips complex and the approximation in a relatively simple manner and greatly reduce the complexity of showing the approximation guarantee. The second technique is what we refer to asscale balancing, which is a simple trick to improve the approximation ratio under certain conditions.- 15 May 2021
- Published by Springer Nature in Journal of Applied and Computational Topology
- Vol. 5 (3) , 425-458
Open AccessImproved approximate rips filtrations with shifted integer lattices and cubical complexes
Rips complexes are important structures for analyzing topological features of metric spaces. Unfortunately, generating these complexes is expensive because of a combinatorial explosion in the complex size. Fornpoints in $$\mathbb {R}^d$$ , we present a scheme to construct a 2-approximation of the filtration of the Rips complex in the $$L_\infty $$ -norm, which extends to a $$2d^{0.25}$$ -approximation in the Euclidean case. Thek-skeleton of the resulting approximation has a total size of $$n2^{O(d\log k +d)}$$ . The scheme is based on the integer lattice and simplicial complexes based on the barycentric subdivision of thed-cube. We extend our result to use cubical complexes in place of simplicial complexes by introducingcubical mapsbetween complexes. We get the same approximation guarantee as the simplicial case, while reducing the total size of the approximation to only $$n2^{O(d)}$$ (cubical) cells. There are two novel techniques that we use in this paper. The first is the use ofacyclic carriersfor proving our approximation result. In our application, these are maps which relate the Rips complex and the approximation in a relatively simple manner and greatly reduce the complexity of showing the approximation guarantee. The second technique is what we refer to asscale balancing, which is a simple trick to improve the approximation ratio under certain conditions. - Open Access
- 4 March 2020
- Published by Springer Nature in Mathematics in Computer Science
- Vol. 14 (1) , 141-176
Coxeter Triangulations Have Good Quality
Coxeter triangulations are triangulations of Euclidean space based on a single simplex. By this we mean that given an individual simplex we can recover the entire triangulation of Euclidean space by inductively reflecting in the faces of the simplex. In this paper we establish that the quality of the simplices in all Coxeter triangulations is $$O(1/\sqrt{d})$$ of the quality of regular simplex. We further investigate the Delaunay property for these triangulations. Moreover, we consider an extension of the Delaunay property, namely protection, which is a measure of non-degeneracy of a Delaunay triangulation. In particular, one family of Coxeter triangulations achieves the protection $$O(1/d^2)$$ . We conjecture that both bounds are optimal for triangulations in Euclidean space.- 4 March 2020
- Published by Springer Nature in Mathematics in Computer Science
- Vol. 14 (1) , 141-176
Open AccessCoxeter Triangulations Have Good Quality
Coxeter triangulations are triangulations of Euclidean space based on a single simplex. By this we mean that given an individual simplex we can recover the entire triangulation of Euclidean space by inductively reflecting in the faces of the simplex. In this paper we establish that the quality of the simplices in all Coxeter triangulations is $$O(1/\sqrt{d})$$ of the quality of regular simplex. We further investigate the Delaunay property for these triangulations. Moreover, we consider an extension of the Delaunay property, namely protection, which is a measure of non-degeneracy of a Delaunay triangulation. In particular, one family of Coxeter triangulations achieves the protection $$O(1/d^2)$$ . We conjecture that both bounds are optimal for triangulations in Euclidean space. - 1 August 2019
- Published by Elsevier in Computational Geometry
- Vol. 81, 33-44
Delaunay simplices in diagonally distorted lattices
- 1 August 2019
- Published by Elsevier in Computational Geometry
- Vol. 81, 33-44
Delaunay simplices in diagonally distorted lattices
- Open Access
- 13 November 2017
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 61 (1) , 42-80
Polynomial-Sized Topological Approximations Using the Permutahedron
- 13 November 2017
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 61 (1) , 42-80
Open AccessPolynomial-Sized Topological Approximations Using the Permutahedron
- Open Access
Polynomial-Sized Topological Approximations Using The Permutahedron
Classical methods to model topological properties of point clouds, such as the Vietoris-Rips complex, suffer from the combinatorial explosion of complex sizes. We propose a novel technique to approximate a multi-scale filtration of the Rips complex with improved bounds for size: precisely, for $n$ points in $\mathbb{R}^d$, we obtain a $O(d)$-approximation with at most $n2^{O(d \log k)}$ simplices of dimension $k$ or lower. In conjunction with dimension reduction techniques, our approach yields a $O(\mathrm{polylog} (n))$-approximation of size $n^{O(1)}$ for Rips filtrations on arbitrary metric spaces. This result stems from high-dimensional lattice geometry and exploits properties of the permutahedral lattice, a well-studied structure in discrete geometry. Building on the same geometric concept, we also present a lower bound result on the size of an approximate filtration: we construct a point set for which every $(1+\epsilon)$-approximation of the \v{C}ech filtration has to contain $n^{\Omega(\log\log n)}$ features, provided that $\epsilon <\frac{1}{\log^{1+c} n}$ for $c\in(0,1)$.Open AccessPolynomial-Sized Topological Approximations Using The Permutahedron
Classical methods to model topological properties of point clouds, such as the Vietoris-Rips complex, suffer from the combinatorial explosion of complex sizes. We propose a novel technique to approximate a multi-scale filtration of the Rips complex with improved bounds for size: precisely, for $n$ points in $\mathbb{R}^d$, we obtain a $O(d)$-approximation with at most $n2^{O(d \log k)}$ simplices of dimension $k$ or lower. In conjunction with dimension reduction techniques, our approach yields a $O(\mathrm{polylog} (n))$-approximation of size $n^{O(1)}$ for Rips filtrations on arbitrary metric spaces. This result stems from high-dimensional lattice geometry and exploits properties of the permutahedral lattice, a well-studied structure in discrete geometry. Building on the same geometric concept, we also present a lower bound result on the size of an approximate filtration: we construct a point set for which every $(1+\epsilon)$-approximation of the \v{C}ech filtration has to contain $n^{\Omega(\log\log n)}$ features, provided that $\epsilon <\frac{1}{\log^{1+c} n}$ for $c\in(0,1)$.