On constant factors in comparison-based geometric algorithms and data structures

DOI10.1145/2582112.2582166MaRDI QIDQ4635526zbMATH OpenOpenAlexFDO

Authors

Publication date 23 April 2018

Published in Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10012/8783

zbMATH Keywords

binary space partitioncomparison-based algorithmsconvex hullline-segment intersectionmaximapoint location

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• On constant factors in comparison-based geometric algorithms and data structures
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
• Orthogonal point location and rectangle stabbing queries in 3-d
• Improved bounds for orthogonal point enclosure query and point location in orthogonal subdivisions in R^3
• scientific article; zbMATH DE number 140454

Cited in

(3)

• On constant factors in comparison-based geometric algorithms and data structures
• Faster output-sensitive skyline computation algorithm
• Novel Transformation Techniques Using Q-Heaps with Applications to Computational Geometry

This page was built for publication: On constant factors in comparison-based geometric algorithms and data structures

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