Paper

Succinct Data Structures for Segments

Bille, Philip, Tarnow, Simon R, Inge Li Gørtz

2024

Overview

We consider succinct data structures for representing a set of \\(n\\) horizontal line segments in the plane given in rank space to support \\emph{segment access}, \\emph{segment selection}, and \\emph{segment rank} queries. A segment access query finds the segment \\((x_1, x_2, y)\\) given its \\(y\\)-coordinate (\\(y\\)-coordinates of the segments are distinct), a segment selection query finds the \\(j\\)th smallest segment (the segment with the \\(j\\)th smallest \\(y\\)-coordinate) among the segments crossing the vertical line for a given \\(x\\)-coordinate, and a segment rank query finds the number of segments crossing the vertical line through \\(x\\)-coordinate \\(i\\) with \\(y\\)-coordinate at most \\(y\\), for a given \\(x\\) and \\(y\\). This problem is a central component in compressed data structures for persistent strings supporting random access. Our main result is data structure using \\(2n\\lg{n} + O(n\\lg{n}/\\lg{\\lg{n}})\\) bits of space and \\(O(\\lg{n}/\\lg{\\lg{n}})\\) query time for all operations. We show that this space bound is optimal up to lower-order terms. We will also show that the query time for segment rank is optimal. The query time for segment selection is also optimal by a previous bound. To obtain our results, we present a novel segment wavelet tree data structure of independent interest. This structure is inspired by and extends the classic wavelet tree for sequences. This leads to a simple, succinct solution with \\(O(\\log n)\\) query times. We then extend this solution to obtain optimal query time. Our space lower bound follows from a simple counting argument, and our lower bound for segment rank is obtained by a reduction from 2-dimensional counting.

• Publisher: Cornell University Library, arXiv.org
• Subject: Data structures / Lower bounds / Queries / Random access / Segments / Sequences