Novel Transformation Techniques Using Q-Heaps with Applications to Computational Geometry

DOI10.1137/S0097539703435728MaRDI QIDQ5317207zbMATH OpenOpenAlexFDO

Authors Qingmin Shi, Joseph Ja'Ja'

Publication date 16 September 2005

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539703435728

zbMATH Keywords

computational geometryfractional cascadinggeometric retrievalorthogonal segment intersectionrectangular point enclosuresearching

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• scientific article; zbMATH DE number 3911764
• Fractional cascading. I: A data structuring technique
• Fractional cascading. II: Applications
• A unified approach to geometric problems using dual cone transformation:
• On constant factors in comparison-based geometric algorithms and data structures

Cited in

(7)

• Fractional cascading. II: Applications
• A unified approach to geometric problems using dual cone transformation:
• Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree
• Orthogonal point location and rectangle stabbing queries in 3-d
• Elastic-degenerate string matching with 1 error
• Elastic-degenerate string matching with 1 error or mismatch
• Approximate suffix-prefix dictionary queries

This page was built for publication: Novel Transformation Techniques Using Q-Heaps with Applications to Computational Geometry

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5317207)