Heat flow and a faster algorithm to compute the surface area of a convex body |
| |
| Authors: | Mikhail Belkin Hariharan Narayanan Partha Niyogi |
| |
| Institution: | 1. Department of Computer Science and Engineering, Ohio State University, Columbus, Ohio;2. Department of Statistics and Mathematics, University of Washington, Seattle, Washington;3. Department of Computer Science, University of Chicago, Chicago, Illinois |
| |
| Abstract: | We draw on the observation that the amount of heat diffusing outside of a heated body in a short period of time is proportional to its surface area, to design a simple algorithm for approximating the surface area of a convex body given by a membership oracle. Our method has a complexity of O*(n4), where n is the dimension, compared to O*(n8) for the previous best algorithm. We show that our complexity cannot be improved given the current state‐of‐the‐art in volume estimation. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 407–428, 2013 |
| |
| Keywords: | randomized algorithms diffusion convex geometry surface area |
|
|
