Heat flow and a faster algorithm to compute the surface area of a convex body

DOI10.1002/rsa.20513zbMath1277.68295OpenAlexW1754996228MaRDI QIDQ2868081

Partha Niyogi, Hariharan Narayanan, Mikhail Belkin

Publication date: 23 December 2013

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20513

zbMATH Keywords

diffusionsurface arearandomized algorithmsconvex geometry

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Length, area, volume and convex sets (aspects of convex geometry) (52A38) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Randomized algorithms (68W20)

Related Items (5)

Rapid mixing of geodesic walks on manifolds with positive curvature ⋮ Stochastic Billiards for Sampling from the Boundary of a Convex Set ⋮ Sampling Hypersurfaces through Diffusion ⋮ A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor ⋮ Estimating perimeter using graph cuts

Cites Work

• Unnamed Item
• A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor
• Random generation of combinatorial structures from a uniform distribution
• A geometric inequality and the complexity of computing volume
• Computing the volume is difficult
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• A new algorithm for minimizing convex functions over convex sets
• Zum Verhältnis von Volumen zu Oberfläche bei konvexen Körpern
• A random polynomial-time algorithm for approximating the volume of convex bodies
• On The Complexity of Computing Mixed Volumes
• Probability Inequalities for Sums of Bounded Random Variables

This page was built for publication: Heat flow and a faster algorithm to compute the surface area of a convex body