Show simple item record

dc.contributor.advisorVempala, Santosh
dc.contributor.authorCristian, Rares
dc.date.accessioned2020-11-09T16:59:51Z
dc.date.available2020-11-09T16:59:51Z
dc.date.created2020-05
dc.date.submittedMay 2020
dc.identifier.urihttp://hdl.handle.net/1853/63878
dc.description.abstractComputing the volume of a polytope is an important longstudied question, with applications ranging from combinatorics to machine learning. While there are numerous randomized algorithms that efficiently approximate the volume, no deterministic algorithm is currently known to exist. This is part of a fundamental question in algorithms: when is randomness truly needed? We investigate whether the notion of chaos can be a substitute for randomness in this setting. There is a key distinction to be made here between chaos and randomness. Given the initial state of a system, we cannot predict the future state of a random process. On the other hand, a chaotic one is fully deterministic, although sensitive to initial conditions. That is, any small change in initial conditions will result in vastly different outcomes. Essentially all current methods for volume approximation rely on being able to sample uniformly from the body, with randomized algorithms doing this via random walks. Instead, we aim to create a deterministic dynamical billiard system that will uniformly cover the polytope. In particular, we consider the trajectory created by the free motion of a point particle inside the polytope with mirror-like reflections off the boundary. Additionally, we add a slight concave curvature to the facets which allows for a greater dispersion of the trajectory
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectGeometry
dc.subjectSampling
dc.subjectChaos
dc.subjectBilliards
dc.titleDeterministic Volume Approximation of Polytopes
dc.typeUndergraduate Research Option Thesis
dc.description.degreeUndergraduate
dc.contributor.departmentComputer Science
dc.contributor.departmentComputer Science
thesis.degree.levelUndergraduate
dc.contributor.committeeMemberTetali, Prasad
dc.date.updated2020-11-09T16:59:51Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record