11011110

Posted by David Eppstein

https://11011110.github.io/blog/2025/06/08/two-recent-preprints.html

https://11011110.github.io/blog/2025/06/08/two-recent-preprints

I have two new(ish) arXiv preprints that I thought I would announce together here rather than devoting a separate post to each of them.

“Zip-tries: simple dynamic data structures for strings” (arXiv:2505.04953, with Ofek Gila, Mike Goodrich, and Ryuto Kitagawa, to be presented by Ofek at ACDA 2025) is on data structures that maintain a dynamic dictionary of words and allow searches in time \(O(w+\log n)\) where \(w\) is the number of words of memory used to represent a search string (potentially much smaller than the number of characters in the string) and \(n\) is the number of strings in the dictionary.

We started our work in this area looking at variations of the skip list annotated with longest common prefix information that would speed searches, but that turned out to be known (it is the main idea of the string B-tree of Ferragina and Grossi from JACM 1999). I think the main theoretical advance of the new paper is to shave down the number of bits that we need to store per node, just as zip trees and zip zip trees shaved down the bits per node of the treaps they were based on.

Like zip trees and zip zip trees, zip-tries also use a “zippering” update where each update pulls the data structure apart along a path and then glues it back together, potentially simpler than trying to achieve the same thing through a sequence of separate local moves like tree rotations. The paper also includes parallel versions of these data structures and experimental results showing that they are fast in practice and in comparison to a leading competitor for the same task, c-trie++.

“Better late than never: the complexity of arrangements of polyhedra” (arXiv:2506.03960 , with Boris Aronov, Sang Won Bae, Sergio Cabello, Otfried Cheong, Christian Knauer, and Raimund Seidel) concerns the interplay between two fundamental bounds in computational geometry. If you have \(n\) hyperplanes in \(d\) dimensions, then they subdivide space into a collection of cells (an “arrangement”) whose total complexity can be proportional to \(n^d\). Each individual cell is a convex polytope. And if you generate a single convex polytope from the same \(n\) hyperplanes, its complexity is lower, proportional to \(n^{\lfloor d/2\rfloor}\); this is the famous upper bound theorem. So what about arrangements of polytopes rather than arrangements of hyperplanes? What this paper proves is that, for \(m\) polytopes having a total of \(n\) facets, the complexity is at most proportional to \(m^{\lceil d/2\rceil}n^{\lfloor d/2\rfloor}\). So when \(m=1\) you recover the upper bound theorem, and when \(m=n\) (so each polytope degenerates to a hyperplane) you recover the arrangement complexity bound.

This paper has quite a messy history. You can find several citations in the literature to exactly this result, cited to a 1992 manuscript “Arrangements of polytopes with applications” by Boris Aronov, Marshall Bern, and me. After multiple revisions, some results from that paper were published by us as “On the number of minimal 1-Steiner trees” [Discrete Comput. Geom. 1994], but without this part of the manuscript. Eventually we lost our own copies, and it became a ghost result in a ghost paper. Finally, Boris got tired of the situation and instigated an effort to re-prove the same result so that it could appear properly in the literature. It was presented at EuroCG last April, and this preprint is the full version. All this caused Danny Halperin to dig up a dusty copy of the old manuscript, or at least the first ten pages of it, which included our old proof of the same bound on the arrangement of polyhedra.

That old proof turns out to be short but not very satisfactory. It starts by assuming that the hyperplanes defining the polyhedra are all in general position, claimed to be without loss of generality because “otherwise perturbing the input will increase the complexity”. But the perturbation argument is nontrivial and a lot of the difficulty in writing the new preprint came about in elaborating this part rather than just sweeping it under a rug.

(Discuss on Mastodon)

https://11011110.github.io/blog/2025/06/08/two-recent-preprints.html

https://11011110.github.io/blog/2025/06/08/two-recent-preprints