Theis Rauhe

SODA Conference 2003 Conference Paper

Labeling schemes for small distances in trees

• Stephen Alstrup
• Philip Bille
• Theis Rauhe

SODA Conference 2002 Conference Paper

Improved labeling scheme for ancestor queries

• Stephen Alstrup
• Theis Rauhe

FOCS Conference 2002 Conference Paper

Small Induced-Universal Graphs and Compact Implicit Graph Representations

• Stephen Alstrup
• Theis Rauhe

We show that there exists a graph G with n /spl middot/ 2/sup O(log* n)/ nodes, where any forest with n nodes is a node-induced subgraph of G. Furthermore, the result implies the existence of a graph with n/sup k/2/sup O(log* n)/ nodes that contains all n-node graphs of fixed arboricity k as node-induced subgraphs. We provide a lower bound of /spl Omega/(n/sup k/) for the size of such a graph. The upper bound is obtained through a simple labeling scheme for parent queries in rooted trees.

SODA Conference 2001 Conference Paper

A cell probe lower bound for dynamic nearest-neighbor searching

• Stephen Alstrup
• Thore Husfeldt
• Theis Rauhe

STOC Conference 2001 Conference Paper

Optimal static range reporting in one dimension

• Stephen Alstrup
• Gerth Stølting Brodal
• Theis Rauhe

We consider static one dimensional range searching problems. These problems are to build static data structures for an integer set S \subseteq U , where U = \{0,1,\dots,2^ w -1\}, which support various queries for integer intervals of U . For the query of reporting all integers in S contained within a query interval, we present an optimal data structure with linear space cost and with query time linear in the number of integers reported. This result holds in the unit cost RAM model with word size w and a standard instruction set. We also present a linear space data structure for approximate range counting. A range counting query for an interval returns the number of integers in S contained within the interval. For any constant ε>0, our range counting data structure returns in constant time an approximate answer which is within a factor of at most 1+ε of the correct answer.

FOCS Conference 2000 Conference Paper

New Data Structures for Orthogonal Range Searching

• Stephen Alstrup
• Gerth Stølting Brodal
• Theis Rauhe

We present new general techniques for static orthogonal range searching problems in two and higher dimensions. For the general range reporting problem in R/sup 3/, we achieve query time O(log n+k) using space O(n log/sup 1+/spl epsiv// n), where n denotes the number of stored points and k the number of points to be reported. For the range reporting problem on an n/spl times/n grid, we achieve query time O(log log n+k) using space O(n log/sup /spl epsiv// n). For the two-dimensional semi-group range sum problem we achieve query time O(log n) using space O(n log n).

SODA Conference 2000 Conference Paper

Pattern matching in dynamic texts

• Stephen Alstrup
• Gerth Stølting Brodal
• Theis Rauhe

STOC Conference 1999 Conference Paper

Worst-Case and Amortised Optimality in Union-Find (Extended Abstract)

• Stephen Alstrup
• Amir M. Ben-Amram
• Theis Rauhe

FOCS Conference 1998 Conference Paper

Marked Ancestor Problems

• Stephen Alstrup
• Thore Husfeldt
• Theis Rauhe

Consider a rooted tree whose nodes can be in two states: marked or unmarked. The marked ancestor problem is to maintain a data structure with the following operations: mark(v) marks node v: unmark(v) removes any marks from node v; firstmarked(v) returns the first marked node on the path from v to the root. We show tight upper and lower bounds for the marked ancestor problem. The lower bounds are proved in the cell probe model, the algorithms run on a unit-cost RAM. As easy corollaries we prove (often optimal) lower bounds on a number of problems. These include planar range searching, including the existential or emptiness problem, priority search trees static tree union-find, and several problems from dynamic computational geometry, including segment intersection, interval maintenance, and ray shooting in the plane. Our upper bounds improve algorithms from various fields, including coloured ancestor problems and maintenance of balanced parentheses.

FOCS Conference 1998 Conference Paper

Optimal Time-Space Trade-Offs for Sorting

• Jakob Pagter
• Theis Rauhe

We study the fundamental problem of sorting in a sequential model of computation and in particular consider the time-space trade-off (product of time and space) for this problem. P. Beame (1991) has shown a lower bound of /spl Omega/(n/sup 2/) for this product leaving a gap of a logarithmic factor up to the previously best known upper bound of O(n/sup 2/ log n) due to G. N. Frederickson (1987). Since then, no progress has been made towards tightening this gap. The main contribution of this paper is a comparison based sorting algorithm which closes the gap by meeting the lower bound of Beame. The time-space product O(n/sup 2/) upper bound holds for the full range of space bounds between log n and n/log n. Hence in this range our algorithm is optimal for comparison based models as well as for the very powerful general models considered by Beame.