Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body

Berkeley, California October 21-October 24

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.34

47th Annual IEEE Symposium on Foundat ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Mikhail Belkin Articles by Hariharan Narayanan Articles by Partha Niyogi

	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, Annual IEEE 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, Annual IEEE 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, Annual IEEE 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, Annual IEEE 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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.