Approximation algorithms | Computational geometry

Convex volume approximation

In the analysis of algorithms, several authors have studied the computation of the volume of high-dimensional convex bodies, a problem that can also be used to model many other problems in combinatorial enumeration.Often these works use a black box model of computation in which the input is given by a subroutine for testing whether a point is inside or outside of the convex body, rather than by an explicit listing of the vertices or faces of a convex polytope.It is known that, in this model, no deterministic algorithm can achieve an accurate approximation, and even for an explicit listing of faces or vertices the problem is #P-hard.However, a joint work by Martin Dyer, Alan M. Frieze and Ravindran Kannan provided a randomized polynomial time approximation scheme for the problem,providing a sharp contrast between the capabilities of randomized and deterministic algorithms. The main result of the paper is a randomized algorithm for finding an approximation to the volume of a convex body in -dimensional Euclidean space by assuming the existence of a membership oracle. The algorithm takes time bounded by a polynomial in , the dimension of and .The algorithm combines two ideas: * By using a Markov chain Monte Carlo (MCMC) method, it is possible to generate points that are nearly uniformly randomly distributed within a given convex body. The basic scheme of the algorithm is a nearly uniform sampling from within by placing a grid consisting of -dimensional cubes and doing a random walk over these cubes. By using the theory of rapidly mixing Markov chains, they show that it takes a polynomial time for the random walk to settle down to being a nearly uniform distribution. * By using rejection sampling, it is possible to compare the volumes of two convex bodies, one nested within another, when their volumes are within a small factor of each other. The basic idea is to generate random points within the outer of the two bodies, and to count how often those points are also within the inner body. The given convex body can be approximated by a sequence of nested bodies, eventually reaching one of known volume (a hypersphere), with this approach used to estimate the factor by which the volume changes at each step of this sequence. Multiplying these factors gives the approximate volume of the original body. This work earned its authors the 1991 Fulkerson Prize. (Wikipedia).

Video thumbnail

Determine the Volume of a Cube (Decimals)

This video explains how to determine the volume of a rectangular cube. http://mathispower4u.com

From playlist Volume and Surface Area (Geometry)

Video thumbnail

Introduction to Volume

This video introduces volume and shows how to determine the volume of a cube and rectangular solid. http://mathispower4u.com

From playlist Volume and Surface Area (Geometry)

Video thumbnail

What is the difference between convex and concave

👉 Learn about polygons and how to classify them. A polygon is a plane shape bounded by a finite chain of straight lines. A polygon can be concave or convex and it can also be regular or irregular. A concave polygon is a polygon in which at least one of its interior angles is greater than 1

From playlist Classify Polygons

Video thumbnail

What is the difference between convex and concave polygons

👉 Learn about polygons and how to classify them. A polygon is a plane shape bounded by a finite chain of straight lines. A polygon can be concave or convex and it can also be regular or irregular. A concave polygon is a polygon in which at least one of its interior angles is greater than 1

From playlist Classify Polygons

Video thumbnail

What are convex polygons

👉 Learn about polygons and how to classify them. A polygon is a plane shape bounded by a finite chain of straight lines. A polygon can be concave or convex and it can also be regular or irregular. A concave polygon is a polygon in which at least one of its interior angles is greater than 1

From playlist Classify Polygons

Video thumbnail

Volume of a sphere

Another practice problem dealing with the volume of a sphere

From playlist Middle School - Worked Examples

Video thumbnail

Nearly Optimal Deterministic Algorithms Via M-Ellipsoids - Santosh Vempala

Santosh Vempala Georgia Institute of Technology January 30, 2011 Milman's ellipsoids play an important role in modern convex geometry. Here we show that their proofs of existence can be turned into efficient algorithms, and these in turn lead to improved deterministic algorithms for volume

From playlist Mathematics

Video thumbnail

Lecture 12 | Convex Optimization I (Stanford)

Professor Stephen Boyd, of the Stanford University Electrical Engineering department, lectures on geometric problems in the context of electrical engineering and convex optimization for the course, Convex Optimization I (EE 364A). Convex Optimization I concentrates on recognizing and so

From playlist Lecture Collection | Convex Optimization

Video thumbnail

Find the volume of a sphere given the circumference

👉 Learn how to find the volume and the surface area of a sphere. A sphere is a perfectly round 3-dimensional object. It is an object with the shape of a round ball. The distance from the center of a sphere to any point on its surface is called the radius of the sphere. A sphere has a unifo

From playlist Volume and Surface Area

Video thumbnail

Introduction to Volume

This video provides a basic introduction to volume.

From playlist Volume and Surface Area (Geometry)

Video thumbnail

Peter Pivovarov: Random s-concave functions and isoperimetry

I will discuss stochastic geometry of s-concave functions. In particular, I will explain how a ”local” stochastic isoperimetry underlies several functional inequalities. A new ingredient is a notion of shadow systems for s-concave functions. Based on joint works with J. Rebollo Bueno.

From playlist Workshop: High dimensional spatial random systems

Video thumbnail

Haotian Jiang: Minimizing Convex Functions with Integral Minimizers

Given a separation oracle SO for a convex function f that has an integral minimizer inside a box with radius R, we show how to find an exact minimizer of f using at most • O(n(n + log(R))) calls to SO and poly(n,log(R)) arithmetic operations, or • O(nlog(nR)) calls to SO and exp(O(n)) · po

From playlist Workshop: Continuous approaches to discrete optimization

Video thumbnail

Calculus 1 Lecture 5.2 Part 3

Calculus 1 Lecture 5.2 Part 3: Finding the Volume of a Solid of Revolution Using Disks or Washers.

From playlist Calculus 1 Playlist 2

Video thumbnail

Reducing Isotropy to KLS: An Almost Cubic Volume Algorithm by Santosh Vempala

Program Advances in Applied Probability II (ONLINE) ORGANIZERS: Vivek S Borkar (IIT Bombay, India), Sandeep Juneja (TIFR Mumbai, India), Kavita Ramanan (Brown University, Rhode Island), Devavrat Shah (MIT, US) and Piyush Srivastava (TIFR Mumbai, India) DATE: 04 January 2021 to 08 Januar

From playlist Advances in Applied Probability II (Online)

Video thumbnail

Santosh Vempala: Reducing Isotropy to KLS: An Almost Cubic Volume Algorithm

Computing the volume of a convex body is an ancient problem whose study has led to many interesting mathematical developments. In the most general setting, the convex body is given only by a membership oracle. In this talk, we present a faster algorithm for isotropic transformation of an a

From playlist Workshop: High dimensional measures: geometric and probabilistic aspects

Video thumbnail

Bo'az Klartag - Convexity in High Dimensions I

October 28, 2022 This is the first talk in the Minerva Mini-course of Bo'az Klartag, Weizmann Institute of Science and Princeton's Fall 2022 Minerva Distinguished Visitor We will discuss recent progress in the understanding of the isoperimetric problem for high-dimensional convex sets, an

From playlist Minerva Mini Course - Bo'az Klartag

Video thumbnail

Ex: Determine Volume of a Cone

This video provides an example of how to determine the volume of a cone. Complete Video Library at http://wwwmathispower4u.com Search the Library at http://www.mathispower4u.wordpress.com

From playlist Volume and Surface Area (Geometry)

Video thumbnail

GPDE Workshop - Synthetic formulations - Cedric Villani

Cedric Villani IAS/ENS-France February 23, 2009 For more videos, visit http://video.ias.edu

From playlist Mathematics

Related pages

Random walk | Markov chain Monte Carlo | Convex polytope | Oracle machine | Klee's measure problem | Deterministic algorithm | Convex body | Volume | Analysis of algorithms | Rejection sampling | Markov chain mixing time