Sublinear Geometric Algorithms

DOI10.1137/S009753970444572XMaRDI QIDQ5470705zbMATH OpenFDO

Authors Ding Liu, Avner Magen, Bernard Chazelle

Publication date 1 June 2006

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

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

zbMATH Keywords

sublinear algorithmsapproximate shortest pathspolyhedral intersection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Sublinear geometric algorithms
• Applications of random sampling in computational geometry. II
• Multi-pass geometric algorithms
• Multi-pass geometric algorithms
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time

Cited in

(19)

• Sublinear time approximation schemes for makespan minimization on parallel machines
• A sublogarithmic convex hull algorithm
• Algorithms for approximate shortest path queries on weighted polyhedral surfaces
• Sublinear geometric algorithms
• Sublinear-time Algorithms
• Linear-time algorithms for geometric graphs with sublinearly many edge crossings
• Sublinear algorithms for scheduling with chain precedence constraints
• Linear-time algorithms for geometric graphs with sublinearly many crossings
• Separating sublinear time computations by approximate diameter
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
• Separating Sublinear Time Computations by Approximate Diameter
• Multi-pass geometric algorithms
• Suboptimal solutions to the algebraic-error line triangulation
• A Subexponential Algorithm for Abstract Optimization Problems
• Sublinear randomized algorithms for skeleton decompositions
• Practical distribution-sensitive point location in triangulations
• Testing Euclidean Spanners
• Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
• Approximating the maximum overlap of polygons under translation

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 Q5470705)