Search

We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings. The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path. We describe an online O(log logn)-competitive search tree data structure in this model, where n is the number of vertices. This matches the best-known competitive ratio of binary search trees. Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one that we call Steiner-closed search trees, which may be of independent interest. Moreover, our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees and, second, from these trees into paths. [ABSTRACT FROM AUTHOR]

We revisitself-adjustingexternal memory tree data structures, which combine the optimal (and practical) worst-case I/O performances of B-trees, while adapting to the online distribution of queries. Our approach is analogous to undergoing efforts in the BST model, where Tango Trees (Demaine et al., SIAM J. Comput. 37(1), 240–251, 2007) were shown to be O (log log N) -competitive with the runtime of the best offline binary search tree on every sequence of searches. Here we formalize the B-Tree model as a natural generalization of the BST model. We prove lower bounds for the B-Tree model, and introduce a B-Tree model data structure, the Belga B-tree, that executes any sequence of searches within a O (log log N) factor of the best offline B-tree model algorithm, provided B = log O (1) N . We also show how to transform any static BST into a static B-tree which is faster by a Θ (log B) factor; the transformation is randomized and we show that randomization is necessary to obtain any significant speedup. [ABSTRACT FROM AUTHOR]

We show that, unlike the Yao–Yao graph Y Y 6 , the Theta–Theta graph Θ Θ 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 Θ Θ 6 is unbounded. [ABSTRACT FROM AUTHOR]

The 3SUM problem asks if an input n-set of real numbers contains a triple whose sum is zero. We qualify such a triple of degenerate because the probability of finding one in a random input is zero. We consider the 3POL problem, an algebraic generalization of 3SUM where we replace the sum function by a constant-degree polynomial in three variables. The motivations are threefold. Raz et al. gave an O (n 11 / 6) upper bound on the number of degenerate triples for the 3POL problem. We give algorithms for the corresponding problem of counting them. Grønlund and Pettie designed subquadratic algorithms for 3SUM. We prove that 3POL admits bounded-degree algebraic decision trees of depth O (n 12 / 7 + ε) , and we prove that 3POL can be solved in O (n 2 (log log n) 3 / 2 / (log n) 1 / 2) time in the real-RAM model, generalizing their results. 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 show how to solve GPT in subquadratic time when the input points lie on a small number of constant-degree polynomial curves. Many other geometric degeneracy testing problems reduce to 3POL. [ABSTRACT FROM AUTHOR]

We consider preprocessing a set S of n points in convex position in the plane into a data structure supporting queries of the following form: given a point q and a directed line ℓ in the plane, report the point of S that is farthest from (or, alternatively, nearest to) the point q among all points to the left of line ℓ. We present two data structures for this problem. The first data structure uses O(n1+ε) space and preprocessing time, and answers queries in O(21/εlogn) time, for any 0<ε<1. The second data structure uses O(nlog3n) space and polynomial preprocessing time, and answers queries in O(logn) time. These are the first solutions to the problem with O(logn) query time and o(n2) space. The second data structure uses a new representation of nearest- and farthest-point Voronoi diagrams of points in convex position. This representation supports the insertion of new points in clockwise order using only O(logn) amortized pointer changes, in addition to O(logn)-time point-location queries, even though every such update may make Θ(n) combinatorial changes to the Voronoi diagram. This data structure is the first demonstration that deterministically and incrementally constructed Voronoi diagrams can be maintained in o(n) amortized pointer changes per operation while keeping O(logn)-time point-location queries. [ABSTRACT FROM AUTHOR]

We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram (and several variants thereof) of a set S of n sites in the plane as sites are added to the set. To that effect, we define a general update operation for planar graphs that can be used to model the incremental construction of several variants of Voronoi diagrams as well as the incremental construction of an intersection of halfspaces in $$\mathbb {R}^3$$ . We show that the amortized number of edge insertions and removals needed to add a new site to the Voronoi diagram is $$O(\sqrt{n})$$ . A matching $$\Omega (\sqrt{n})$$ combinatorial lower bound is shown, even in the case where the graph representing the Voronoi diagram is a tree. This contrasts with the $$O(\log {n})$$ upper bound of Aronov et al. (LATIN 2006: Theoretical Informatics. Lecture Notes in Computer Science, Springer, Berlin, 2006) for farthest-point Voronoi diagrams in the special case where the points are inserted in clockwise order along their convex hull. We then present a semi-dynamic data structure that maintains the Voronoi diagram of a set S of n sites in convex position. This data structure supports the insertion of a new site p (and hence the addition of its Voronoi cell) and finds the asymptotically minimal number K of edge insertions and removals needed to obtain the diagram of $$S \cup \{p\}$$ from the diagram of S, in time $$O(K\,\mathrm {polylog}\ n)$$ worst case, which is $$O(\sqrt{n}\;\mathrm {polylog}\ n)$$ amortized by the aforementioned combinatorial result. The most distinctive feature of this data structure is that the graph of the Voronoi diagram is maintained explicitly at all times and can be retrieved and traversed in the natural way; this contrasts with other known data structures supporting nearest neighbor queries. Our data structure supports general search operations on the current Voronoi diagram, which can, for example, be used to perform point location queries in the cells of the current Voronoi diagram in $$O(\log n)$$ time, or to determine whether two given sites are neighbors in the Delaunay triangulation. [ABSTRACT FROM AUTHOR]

A static binary search tree where every search starts from where the previous one ends ( lazy finger) is considered. Such a search method is more powerful than that of the classic optimal static trees, where every search starts from the root ( root finger), and less powerful than when rotations are allowed-where finding the best rotation based tree is the topic of the dynamic optimality conjecture of Sleator and Tarjan. The runtime of the classic root-finger tree can be expressed in terms of the entropy of the distribution of the searches, but we show that this is not the case for the optimal lazy finger tree. A non-entropy based asymptotically-tight expression for the runtime of the optimal lazy finger trees is derived, and a dynamic programming-based method is presented to compute the optimal tree. [ABSTRACT FROM AUTHOR]

Consider laying out a fixed-topology binary 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 [ABSTRACT FROM AUTHOR]

We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured according to the ℓ norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p=1, p even, and p=∞. For p even, we reduce the problem to standard convolution, while for p=∞ and p=1, we reduce the problem to (min,+) convolution and $(\operatorname {median},+)$ convolution. Then we solve the latter two convolution problems in subquadratic time, which are interesting results in their own right. These results shed some light on the classic sorting X+ Y problem, because the convolutions can be viewed as computing order statistics on the antidiagonals of the X+ Y matrix. All of our algorithms run in o( n) time, whereas the obvious algorithms for these problems run in Θ( n) time. [ABSTRACT FROM AUTHOR]

In this paper new dependencies are added to the hierarchy of the distribution-sensitive properties for data structures. Most remarkably, we prove that the working-set property is equivalent to the unified-bound property; a fact that had gone unnoticed since the introduction of such bounds in the Eighties by Sleator and Tarjan. [ABSTRACT FROM AUTHOR]

For a fixed integer k≥0, a k-transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to k 'walls', represented as line segments in the plane. We develop lower and upper bounds for the number of k-transmitters that are necessary and sufficient to cover a given collection of line segments, polygonal chains and polygons. [ABSTRACT FROM AUTHOR]

Graph-theoretic properties of certain proximity graphs defined on planar point sets are investigated. We first consider some of the most common proximity graphs of the family of the Delaunay graph, and study their number of edges, minimum and maximum degree, clique number, and chromatic number. In the second part of the paper we focus on the higher order versions of some of these graphs and give bounds on the same parameters. [ABSTRACT FROM AUTHOR]

Over the last decade, there have been several data structures that, given a planar subdi-vision 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 2-D 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. [ABSTRACT FROM AUTHOR]

A data structure is presented for point location in connected planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is within a constant factor of optimal. More specifically, an algorithm is presented that preprocesses a connected planar subdivision G of size n and a query distribution D to produce a point location data structure for G. The expected number of point-line comparisons performed by this data structure, when the queries are distributed according to D, is &Htilde; + O( &Htilde; 1/2 + 1) where &Htilde; = &Htilde;(G, D) is a lower bound on the expected number of point-line comparisons performed by any linear decision tree for point location in Gunder the query distribution D. The preprocessing algorithm runs in O(n log n) time and produces a data structure of size O(n). These results are obtained by creating a Steiner triangulation of G that has near-minimum entropy [ABSTRACT FROM AUTHOR]

This paper gives tight bounds on the cost of cache-oblivious searching. The paper shows that no cache-oblivious search structure can guarantee a search performance of fewer than lg elog N memory transfers between any two levels of the memory hierarchy. This lower bound holds even if all of the block sizes are limited to be powers of 2. The paper gives modified versions of the van Emde Boas layout, where the expected number of memory transfers between any two levels of the memory hierarchy is arbitrarily close to [lg e+ O(lg lg B/lg B)]log N+ O(1). This factor approaches lg e≈1.443 as B increases. The expectation is taken over the random placement in memory of the first element of the structure. Because searching in the disk-access machine (DAM) model can be performed in log N+ O(1) block transfers, this result establishes a separation between the (2-level) DAM model and cache-oblivious model. The DAM model naturally extends to k levels. The paper also shows that as k grows, the search costs of the optimal k-level DAM search structure and the optimal cache-oblivious search structure rapidly converge. This result demonstrates that for a multilevel memory hierarchy, a simple cache-oblivious structure almost replicates the performance of an optimal parameterized k-level DAM structure. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Biedl et al.1 presented an algorithm for unfolding orthostacks into one piece without overlap by using arbitrary cuts along the surface. They conjectured that orthostacks could be unfolded using cuts that lie in a plane orthogonal to a coordinate axis and containing a vertex of the orthostack. We prove the existence of a vertex unfolding using only such cuts. [ABSTRACT FROM AUTHOR]

We introduce a new data structuring paradigm in which operations can be performed on a data structure not only in the present, but also in the past. In this new paradigm, called retroactive data structures, the historical sequence of operations performed on the data structure is not fixed. The data structure allows arbitrary insertion and deletion of operations at arbitrary times, subject only to consistency requirements. We initiate the study of retroactive data structures by formally defining the model and its variants. We prove that, unlike persistence, efficient retroactivity is not always achievable. Thus, we present efficient retroactive data structures for queues, doubly ended queues, priority queues, union-find, and decomposable search structures. [ABSTRACT FROM AUTHOR]

We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we provide necessary and sufficient conditions for the existence of a chord and for the existence of a geodesic path that separate the two sets; when they exist we also derive efficient algorithms for their obtention. We also study the separation of the two sets using the minimum number of pairwise non-crossing chords. [ABSTRACT FROM AUTHOR]