Oracle complexities for computional geometry of semi-algebraic sets and voronoi diagrams

DOI10.1016/0020-0190(90)90104-6zbMath0716.68044OpenAlexW2034187229MaRDI QIDQ753493

D. Kharzeev

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90104-6

zbMATH Keywords

computational geometryVoronoi diagramsconvex hullsoracle complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Software, source code, etc. for problems pertaining to geometry (51-04)

Cites Work

• Unnamed Item
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• A sweepline algorithm for Voronoi diagrams
• Convex hulls of piecewise-smooth Jordan curves
• The Calculation of Multivariate Polynomial Resultants

This page was built for publication: Oracle complexities for computional geometry of semi-algebraic sets and voronoi diagrams