Search

We consider the problem of sorting $n$ items, given the outcomes of $m$ pre-existing comparisons. We present a simple, natural deterministic algorithm that runs in $O(m+\log T)$ time and does $O(\log T)$ comparisons, where $T$ is the number of total orders consistent with the pre-existing comparisons. Our running time and comparison bounds are best possible up to constant factors, thus resolving a problem that has been studied intensely since 1976 (Fredman, Theoretical Computer Science). The best previous algorithm with a bound of $O(\lg T)$ on the number of comparisons has a time bound of $O(n^{2.5})$ and is more complicated. (A recent independent and concurrent work by Van der Hoog and Rutschmann implies an $O(n^{2.371552})$-time algorithm with $O(\log T)$ comparisons.) Our algorithm combines three classic algorithms: topological sort, heapsort with the right kind of heap, and efficient insertion into a sorted list. It outputs the items in sorted order one by one. As a result, it can be modified to solve the important and more general top-$k$ sorting problem: Given $k$ and the outcomes of some pre-existing comparisons, output the smallest $k$ items in sorted order. The modified algorithm solves the top-$k$ sorting problem in minimum time and comparisons, to within constant factors.

We present subquadratic algorithms in the algebraic decision-tree model for several \textsc{3Sum}-hard geometric problems, all of which can be reduced to the following question: Given two sets $A$, $B$, each consisting of $n$ pairwise disjoint segments in the plane, and a set $C$ of $n$ triangles in the plane, we want to count, for each triangle $\Delta\in C$, the number of intersection points between the segments of $A$ and those of $B$ that lie in $\Delta$. The problems considered in this paper have been studied by Chan~(2020), who gave algorithms that solve them, in the standard real-RAM model, in $O((n^2/\log^2n)\log^{O(1)}\log n)$ time. We present solutions in the algebraic decision-tree model whose cost is $O(n^{60/31+\varepsilon})$, for any $\varepsilon>0$. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal, Aronov, Ezra, and Zahl~(2020). A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the \emph{order type} of the lines, a "handicap" that turns out to be beneficial for speeding up our algorithm., Comment: 28 pages, 1 figure, full version of a paper in ISAAC'21

The fragile complexity of a comparison-based algorithm is $f(n)$ if each input element participates in $O(f(n))$ comparisons. In this paper, we explore the fragile complexity of algorithms adaptive to various restrictions on the input, i.e., algorithms with a fragile complexity parameterized by a quantity other than the input size n. We show that searching for the predecessor in a sorted array has fragile complexity ${\Theta}(\log k)$, where $k$ is the rank of the query element, both in a randomized and a deterministic setting. For predecessor searches, we also show how to optimally reduce the amortized fragile complexity of the elements in the array. We also prove the following results: Selecting the $k$-th smallest element has expected fragile complexity $O(\log \log k)$ for the element selected. Deterministically finding the minimum element has fragile complexity ${\Theta}(\log(Inv))$ and ${\Theta}(\log(Runs))$, where $Inv$ is the number of inversions in a sequence and $Runs$ is the number of increasing runs in a sequence. Deterministically finding the median has fragile complexity $O(\log(Runs) + \log \log n)$ and ${\Theta}(\log(Inv))$. Deterministic sorting has fragile complexity ${\Theta}(\log(Inv))$ but it has fragile complexity ${\Theta}(\log n)$ regardless of the number of runs., Comment: Appears at proceedings of the 12th International Conference on Algorithms and Complexity (CIAC 2021)

We show that, unlike the Yao-Yao graph $YY_6$, the Theta-Theta graph $\Theta\Theta_6$ defined by six cones is a spanner for sets of points in convex position. We also show that, for sets of points in non-convex position, the spanning ratio of $\Theta\Theta_6$ is unbounded., Comment: 13 pages, 9 figures

For most algorithms dealing with sets of points in the plane, the only relevant information carried by the input is the combinatorial configuration of the points: the orientation of each triple of points in the set (clockwise, counterclockwise, or collinear). This information is called the order type of the point set. In the dual, realizable order types and abstract order types are combinatorial analogues of line arrangements and pseudoline arrangements. Too often in the literature we analyze algorithms in the real-RAM model for simplicity, putting aside the fact that computers as we know them cannot handle arbitrary real numbers without some sort of encoding. Encoding an order type by the integer coordinates of some realizing point set is known to yield doubly exponential coordinates in some cases. Other known encodings can achieve quadratic space or fast orientation queries, but not both. In this contribution, we give a compact encoding for abstract order types that allows efficient query of the orientation of any triple: the encoding uses O(n^2) bits and an orientation query takes O(log n) time in the word-RAM model. This encoding is space-optimal for abstract order types. We show how to shorten the encoding to O(n^2 (loglog n)^2 / log n) bits for realizable order types, giving the first subquadratic encoding for those order types with fast orientation queries. We further refine our encoding to attain O(log n/loglog n) query time without blowing up the space requirement. In the realizable case, we show that all those encodings can be computed efficiently. Finally, we generalize our results to the encoding of point configurations in higher dimension.

The 3SUM problem asks if an input $n$-set of real numbers contains a triple whose sum is zero. We consider the 3POL problem, a natural generalization of 3SUM where we replace the sum function by a constant-degree polynomial in three variables. The motivations are threefold. Raz, Sharir, and de Zeeuw gave a $O(n^{11/6})$ upper bound on the number of solutions of trivariate polynomial equations when the solutions are taken from the cartesian product of three $n$-sets of real numbers. We give algorithms for the corresponding problem of counting such solutions. Gr\o nlund and Pettie recently designed subquadratic algorithms for 3SUM. We generalize their results to 3POL. Finally, we shed light on the General Position Testing (GPT) problem: "Given $n$ points in the plane, do three of them lie on a line?", a key problem in computational geometry. We prove that there exist bounded-degree algebraic decision trees of depth $O(n^{\frac{12}{7}+\varepsilon})$ that solve 3POL, and that 3POL can be solved in $O(n^2 {(\log \log n)}^\frac{3}{2} / {(\log n)}^\frac{1}{2})$ time in the real-RAM model. Among the possible applications of those results, we show how to solve GPT in subquadratic time when the input points lie on $o({(\log n)}^\frac{1}{6}/{(\log \log n)}^\frac{1}{2})$ constant-degree polynomial curves. This constitutes a first step towards closing the major open question of whether GPT can be solved in subquadratic time. To obtain these results, we generalize important tools --- such as batch range searching and dominance reporting --- to a polynomial setting. We expect these new tools to be useful in other applications., Comment: Submitted to SoCG'17

The $k$-SUM problem is given $n$ input real numbers to determine whether any $k$ of them sum to zero. The problem is of tremendous importance in the emerging field of complexity theory within $P$, and it is in particular open whether it admits an algorithm of complexity $O(n^c)$ with $c<\lceil \frac{k}{2} \rceil$. Inspired by an algorithm due to Meiser (1993), we show that there exist linear decision trees and algebraic computation trees of depth $O(n^3\log^3 n)$ solving $k$-SUM. Furthermore, we show that there exists a randomized algorithm that runs in $\tilde{O}(n^{\lceil \frac{k}{2} \rceil+8})$ time, and performs $O(n^3\log^3 n)$ linear queries on the input. Thus, we show that it is possible to have an algorithm with a runtime almost identical (up to the $+8$) to the best known algorithm but for the first time also with the number of queries on the input a polynomial that is independent of $k$. The $O(n^3\log^3 n)$ bound on the number of linear queries is also a tighter bound than any known algorithm solving $k$-SUM, even allowing unlimited total time outside of the queries. By simultaneously achieving few queries to the input without significantly sacrificing runtime vis-\`{a}-vis known algorithms, we deepen the understanding of this canonical problem which is a cornerstone of complexity-within-$P$. We also consider a range of tradeoffs between the number of terms involved in the queries and the depth of the decision tree. In particular, we prove that there exist $o(n)$-linear decision trees of depth $o(n^4)$.

We improve the lower bound on the amortized cost of the decrease-key operation in the pure heap model and show that any pure-heap-model heap (that has a \bigoh{\log n} amortized-time extract-min operation) must spend \bigom{\log\log n} amortized time on the decrease-key operation. Our result shows that sort heaps as well as pure-heap variants of numerous other heaps have asymptotically optimal decrease-key operations in the pure heap model. In addition, our improved lower bound matches the lower bound of Fredman [J. ACM 46(4):473-501 (1999)] for pairing heaps [M.L. Fredman, R. Sedgewick, D.D. Sleator, and R.E. Tarjan. Algorithmica 1(1):111-129 (1986)] and surpasses it for pure-heap variants of numerous other heaps with augmented data such as pointer rank-pairing heaps., Comment: arXiv admin note: substantial text overlap with arXiv:1302.6641

Partial persistence is a general transformation that takes a data structure and allows queries to be executed on any past state of the structure. The cache-oblivious model is the leading model of a modern multi-level memory hierarchy.We present the first general transformation for making cache-oblivious model data structures partially persistent.

We present a general transformation for combining a constant number of binary search tree data structures (BSTs) into a single BST whose running time is within a constant factor of the minimum of any "well-behaved" bound on the running time of the given BSTs, for any online access sequence. (A BST has a well behaved bound with $f(n)$ overhead if it spends at most \bigoh{f(n)} time per access and its bound satisfies a weak sense of closure under subsequences.) In particular, we obtain a BST data structure that is \bigoh{\log\log n} competitive, satisfies the working set bound (and thus satisfies the static finger bound and the static optimality bound), satisfies the dynamic finger bound, satisfies the unified bound with an additive \bigoh{\log\log n} factor, and performs each access in worst-case \bigoh{\log n} time., Comment: 12 pages, 2 figures, ICALP 2013

Over the last decade, there have been several data structures that, given a planar subdivision and a probability distribution over the plane, provide a way for answering point location queries that is fine-tuned for the distribution. All these methods suffer from the requirement that the query distribution must be known in advance. We present a new data structure for point location queries in planar triangulations. Our structure is asymptotically as fast as the optimal structures, but it requires no prior information about the queries. This is a 2D analogue of the jump from Knuth's optimum binary search trees (discovered in 1971) to the splay trees of Sleator and Tarjan in 1985. While the former need to know the query distribution, the latter are statically optimal. This means that we can adapt to the query sequence and achieve the same asymptotic performance as an optimum static structure, without needing any additional information., Comment: 13 pages, 1 figure, a preliminary version appeared at SoCG 2011

A data structure is presented for the Mergeable Dictionary abstract data type, which supports the following operations on a collection of disjoint sets of totally ordered data: Predecessor-Search, Split and Merge. While Predecessor-Search and Split work in the normal way, the novel operation is Merge. While in a typical mergeable dictionary (e.g. 2-4 Trees), the Merge operation can only be performed on sets that span disjoint intervals in keyspace, the structure here has no such limitation, and permits the merging of arbitrarily interleaved sets. Tarjan and Brown present a data structure which can handle arbitrary Merge operations in O(log n) amortized time per operation if the set of operations is restricted to exclude the Split operation. In the presence of Split operations, the amortized time complexity of their structure becomes \Omega(n). A data structure which supports both Split and Merge operations in O(log^2 n) amortized time per operation was given by Farach and Thorup. In contrast, our data structure supports all operations, including Split and Merge, in O(log n) amortized time, thus showing that interleaved Merge operations can be supported at no additional cost vis-a-vis disjoint Merge operations., Comment: 34 pages, 6 figures

We construct the first two continuous bloomings of all convex polyhedra. First, the source unfolding can be continuously bloomed. Second, any unfolding of a convex polyhedron can be refined (further cut, by a linear number of cuts) to have a continuous blooming., Comment: 13 pages, 6 figures

The assignment problem takes as input two finite point sets S and T and establishes a correspondence between points in S and points in T, such that each point in S maps to exactly one point in T, and each point in T maps to at least one point in S. In this paper we show that this problem has an O(n log n)-time solution, provided that the points in S and T are restricted to lie on a line (linear time, if S and T are presorted)., Comment: 13 pages, 8 figures

Consider laying out a fixed-topology tree of N nodes into external memory with block size B so as to minimize the worst-case number of block memory transfers required to traverse a path from the root to a node of depth D. We prove that the optimal number of memory transfers is $$ \cases{ \displaystyle \Theta\left( {D \over \lg (1{+}B)} \right) & when $D = O(\lg N)$, \cr \displaystyle \Theta\left( {\lg N \over \lg \left(1{+}{B \lg N \over D}\right)} \right) & when $D = \Omega(\lg N)$ and $D = O(B \lg N)$, \cr \displaystyle \Theta\left( {D \over B} \right) & when $D = \Omega(B \lg N)$. } $$, Comment: 10 pages, 1 figure. To appear in Algorithmica