Extreme points under random noise

DOI10.1007/978-3-540-30140-0_25MaRDI QIDQ5464585zbMATH OpenOpenAlexFDO

Authors Valentina Damerow, Christian Sohler

Publication date 18 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b100428

zbMATH Keywords

Average ComplexityConvex HullSmoothed Analysis

Mathematics Subject Classification ID

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

Recommendations

• On the smoothed complexity of convex hulls
• On the convex hull of random points in a polytope
• On the variance of the number of extreme points of a random convex hull
• scientific article; zbMATH DE number 4036606
• Random polytopes in a convex polytope, independence of shape, and concentration of vertices

Cited in

(14)

• Smoothed analysis of probabilistic roadmaps
• Extreme probability submeasures on 3 points
• Smoothed analysis of partitioning algorithms for Euclidean functionals
• Smoothed analysis of binary search trees
• A fast and efficient algorithm for determining the connected orthogonal convex hulls
• On the Most Likely Voronoi Diagram and Nearest Neighbor Searching
• Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
• A friendly smoothed analysis of the simplex method
• On the smoothed complexity of convex hulls
• scientific article; zbMATH DE number 7650102 (Why is no real title available?)
• Upper and lower bounds on the smoothed complexity of the simplex method
• Upper and lower bounds on the smoothed complexity of the simplex method
• Efficient real-time and parallel algorithm for connected orthogonal convex hulls on large point sets
• Extreme points of coherent probabilities in finite spaces

This page was built for publication: Extreme points under random noise

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