Succinct and Implicit Data Structures for Computational Geometry

DOI10.1007/978-3-642-40273-9_15zbMath1394.68097OpenAlexW180217369MaRDI QIDQ2848977

Meng He

Publication date: 13 September 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-40273-9_15

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (3)

Encoding two-dimensional range top-\(k\) queries ⋮ Unnamed Item ⋮ Succinct Color Searching in One Dimension

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal partition trees
• Untangled monotonic chains and adaptive range search
• An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
• Improved data structures for the orthogonal range successor problem
• Range searching with efficient hierarchical cuttings
• Rank/select on dynamic compressed sequences and applications
• Partial match retrieval in implicit data structures
• Succinct representations of planar maps
• Reporting points in halfspaces
• Efficient partition trees
• Decomposable searching problems
• Approximating minimum cocolorings.
• Expected asymptotically optimal planar point location
• An in-place min-max priority search tree
• Succinct representation of labeled graphs
• Rank and select revisited and extended
• Succinct Representation of Balanced Parentheses and Static Trees
• Succinct Indices for Range Queries with Applications to Orthogonal Range Maxima
• Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model
• Succinct Data Structures for Path Queries
• Compressed representations of sequences and full-text indexes
• Dynamic Range Majority Data Structures
• Dynamic Range Selection in Linear Space
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Succinct indexes for strings, binary relations and multilabeled trees
• Succinct geometric indexes supporting point location queries
• Succinct Representations of Arbitrary Graphs
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
• Priority Search Trees
• Optimal Point Location in a Monotone Subdivision
• Searching and storing similar lists
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Implicit Data Structures for the Dictionary Problem
• Optimal Search in Planar Subdivisions
• New Results on Dynamic Planar Point Location
• Multidimensional binary search trees used for associative searching
• On the Exact Worst Case Query Complexity of Planar Point Location
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
• A Space-Efficient Framework for Dynamic Point Location
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Space Efficient Data Structures for Dynamic Orthogonal Range Counting
• Towards in-place geometric algorithms and data structures
• Algorithms and Data Structures
• Orthogonal range searching on the RAM, revisited
• Orthogonal range reporting
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
• Algorithms and Data Structures

This page was built for publication: Succinct and Implicit Data Structures for Computational Geometry