loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body
Berkeley, California
October 21-October 24
ISBN: 0-7695-2720-5
ASCII Text
x 
 
Mikhail Belkin, Hariharan Narayanan, Partha Niyogi, "Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body," Foundations of Computer Science, IEEE Annual Symposium on, pp. 47-56, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2006.34,
author = {Mikhail Belkin and Hariharan Narayanan and Partha Niyogi},
title = {Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2006},
issn = {0272-5428},
pages = {47-56},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.34},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body
SN - 0272-5428
SP47
EP56
A1 - Mikhail Belkin,
A1 - Hariharan Narayanan,
A1 - Partha Niyogi,
PY - 2006
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
Mikhail Belkin, Ohio State University, USA
Hariharan Narayanan, University of Chicago, USA
Partha Niyogi, University of Chicago, USA
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*(n^4), where n is the dimension, compared to O*(n^8.5) for the previous best algorithm. We show that our complexity cannot be improved given the current state-of-the-art in volume estimation.
Citation:
Mikhail Belkin, Hariharan Narayanan, Partha Niyogi, "Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body," focs, pp.47-56, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.