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

DOI10.1016/0020-0190(90)90104-6zbMATH Open0716.68044OpenAlexW2034187229MaRDI QIDQ753493FDOQ753493

Authors: 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

Recommendations

• scientific article; zbMATH DE number 1882491
• scientific article; zbMATH DE number 795220
• Publication:3479543
• scientific article; zbMATH DE number 4037201
• Polyhedral and algebraic methods in computational geometry

zbMATH Keywords

computational geometryconvex hullsVoronoi diagramsoracle 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

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

Cited In (2)

• Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model
• Oracle-polynomial-time approximation of largest simplices in convex bodies

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

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