Sublinear geometric algorithms

DOI10.1145/780542.780620MaRDI QIDQ3581255zbMATH OpenOpenAlexFDO

Authors Ding Liu, Avner Magen, Bernard Chazelle

Publication date 16 August 2010

Published in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/780542.780620

Mathematics Subject Classification ID

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

Recommendations

• Sublinear Geometric Algorithms
• Geometric approximation algorithms
• scientific article; zbMATH DE number 66476
• scientific article; zbMATH DE number 1444288
• scientific article; zbMATH DE number 480245
• Instance-optimal geometric algorithms
• scientific article; zbMATH DE number 1006218

Cited in

(13)

• Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
• Suboptimal solutions to the algebraic-error line triangulation
• Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets
• Sublinear randomized algorithms for skeleton decompositions
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
• Linear-time algorithms for geometric graphs with sublinearly many crossings
• Multi-pass geometric algorithms
• Linear-time algorithms for geometric graphs with sublinearly many edge crossings
• Sublinear Geometric Algorithms
• Range counting oracles for geometric problems
• Property testing of curve similarity
• Improved algorithms for quantum identification of Boolean oracles
• A sublogarithmic convex hull algorithm

This page was built for publication: Sublinear geometric algorithms

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