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


Aruni Choudhary has a total of 6 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    No-Dimensional Tverberg Theorems and Algorithms

    by Aruni Choudhary, Wolfgang Mulzer

    Tverberg’s theorem states that for any $$k\ge 2$$ k ≥ 2 and any set $$P\subset {\mathbb {R}}^d$$ P ⊂ R d of at least $$(d+1)(k-1)+1$$ ( 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}$$ CLS = PPAD ∩ 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$$ P ⊂ R d and any $$k\in \{2,\dots ,n\}$$ k ∈ { 2 , ⋯ , n } in $$O(nd\lceil {\log k}\rceil )$$ O ( n d ⌈ log k ⌉ ) time a k-partition of P such that there is a ball of radius $$O((k/\sqrt{n}){\text {diam}}(P))$$ O ( ( k / n ) 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

    Improved approximate rips filtrations with shifted integer lattices and cubical complexes

    by Aruni Choudhary, Michael Kerber, Sharath Raghvendra

    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$$Rd , we present a scheme to construct a 2-approximation of the filtration of the Rips complex in the $$L_\infty $$L∞ -norm, which extends to a $$2d^{0.25}$$2d0.25 -approximation in the Euclidean case. Thek-skeleton of the resulting approximation has a total size of $$n2^{O(d\log k +d)}$$n2O(dlogk+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)}$$n2O(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

    Coxeter Triangulations Have Good Quality

    by Aruni Choudhary, Siargey Kachanovich, Mathijs Wintraecken

    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})$$O(1/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)$$O(1/d2) . We conjecture that both bounds are optimal for triangulations in Euclidean space.


  • Open Access

    Polynomial-Sized Topological Approximations Using the Permutahedron

    by Aruni Choudhary, Michael Kerber, Sharath Raghvendra


  • Open Access

    Polynomial-Sized Topological Approximations Using The Permutahedron

    by Aruni Choudhary, Michael Kerber, Sharath Raghvendra

    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)$.