2026-07-23T15:49:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23121 2025-10-02T12:38:11Z ddc:004 open_access

Succinct Data Structures for Segments Bille, Philip Gørtz, Inge Li Tarnow, Simon R. Succinct Data structures Selection We consider succinct data structures for representing a set of n horizontal line segments in the plane given in rank space to support segment access, segment selection, and segment rank queries. A segment access query finds the segment (x₁, x₂, y) given its y-coordinate (y-coordinates of the segments are distinct), a segment selection query finds the jth smallest segment (the segment with the jth 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 a 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Philip Bille and Inge Li Gørtz and Simon R. Tarnow 2025 Is Part Of LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2025.27 urn:nbn:de:0030-drops-231218 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.27 eng https://creativecommons.org/licenses/by/4.0/legalcode