Heat flow and a faster algorithm to compute the surface area of a convex body1. Issue 4 (8th July 2013)

• Record Type: Journal Article
• Authors: Belkin, Mikhail; Narayanan, Hariharan; Niyogi, Partha
• Is Part Of: Random structures & algorithms. Volume 43:Issue 4(2013)
• Page Start: 407
• Page End: 428
• Publication Date: 2013-07-08
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20513
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>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 <italic>O</italic>^*(<italic>n</italic>⁴), where <italic>n</italic> is the dimension, compared to <italic>O</italic>^*(<italic>n</italic>⁸) 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</p> </abstract>