Yakov Nekrich

Yakov Nekrich, Saladi Rahul

Shallow cuttings are a fundamental tool in computational geometry and spatial databases for solving offline and online range searching problems. For a set $P$ of $N$ points in 3-D, at SODA'14, Afshani and Tsakalidis designed an optimal $O(N\log_2N)$ time algorithm that constructs shallow cuttings for 3-D dominance ranges in internal memory. Even though shallow cuttings are used in the I/O-model to design space and query efficient range searching data structures, an efficient construction of them is not known till now. In this paper, we design an optimal-cost algorithm to construct shallow cuttings for 3-D dominance ranges. The number of I/Os performed by the algorithm is $O\left(\frac{N}{B}\log_{M/B}\left(\frac{N}{B}\right) \right)$, where $B$ is the block size and $M$ is the memory size. As two applications of the optimal-cost construction algorithm, we design fast algorithms for offline 3-D dominance reporting and offline 3-D approximate dominance counting. We believe that our algorithm will find further applications in offline 3-D range searching problems and in improving construction cost of data structures for 3-D range searching problems.

Sujoy Bhore, Chih-Hung Liu, Anurag Murty Naredla et al.

Given a simple polygon $P$ with $n$ vertices, we consider the problem of constructing a data structure for visibility queries: for any query point $q \in P$, compute the visibility polygon of $q$ in $P$. To obtain $O(\log n + k)$ query time, where $k$ is the size of the visibility polygon of $q$, the previous best result requires $O(n^3)$ space. In this paper, we propose a new data structure that uses $O(n^{2+ε})$ space, for any $ε> 0$, while achieving the same query time. If only $O(n^2)$ space is available, the best known result provides $O(\log^2 n + k)$ query time. We improve this to $O(\log n \log \log n + k)$ time. When restricted to $o(n^2)$ space, the only previously known approach, aside from the $O(n)$-time algorithm that computes the visibility polygon without preprocessing, is an $O(n)$-space data structure that supports $O(k \log n)$-time queries. We construct a data structure using $O(n \log n)$ space that answers visibility queries in $O(n^{1/2+ε} + k)$ time. In addition, for the special case in which $q$ lies on the boundary of $P$, we build a data structure of $O(n \log n)$ space supporting $O(\log^2 n + k)$ query time; alternatively, we achieve $O(\log n + k)$ query time using $O(n^{1+ε})$ space. To achieve our results, we propose a new method for decomposing simple polygons, which may be of independent interest.

Gonzalo Navarro, Yakov Nekrich

Let $\mathcal{D}$ be a collection of $D$ documents, which are strings over an alphabet of size $σ$, of total length $n$. We describe a data structure that uses linear space and and reports $k$ most relevant documents that contain a query pattern $P$, which is a string of length $p$, in time $O(p/\log_σn+k)$, which is optimal in the RAM model in the general case where $\lg D = Θ(\log n)$, and involves a novel RAM-optimal suffix tree search. Our construction supports an ample set of important relevance measures... [clip] When $\lg D = o(\log n)$, we show how to reduce the space of the data structure from $O(n\log n)$ to $O(n(\logσ+\log D+\log\log n))$ bits... [clip] We also consider the dynamic scenario, where documents can be inserted and deleted from the collection. We obtain linear space and query time $O(p(\log\log n)^2/\log_σn+\log n + k\log\log k)$, whereas insertions and deletions require $O(\log^{1+ε} n)$ time per symbol, for any constant $ε>0$. Finally, we consider an extended static scenario where an extra parameter $par(P,d)$ is defined, and the query must retrieve only documents $d$ such that $par(P,d)\in [τ_1,τ_2]$, where this range is specified at query time. We solve these queries using linear space and $O(p/\log_σn + \log^{1+ε} n + k\log^εn)$ time, for any constant $ε>0$. Our technique is to translate these top-$k$ problems into multidimensional geometric search problems. As an additional bonus, we describe some improvements to those problems.