• Login
    View Item 
    •   SMARTech Home
    • Undergraduate Research Opportunities Program (UROP)
    • Undergraduate Research Option Theses
    • View Item
    •   SMARTech Home
    • Undergraduate Research Opportunities Program (UROP)
    • Undergraduate Research Option Theses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Deterministic Volume Approximation of Polytopes

    Thumbnail
    View/Open
    CRISTIAN-UNDERGRADUATERESEARCHOPTIONTHESIS-2020.pdf (1.467Mb)
    Date
    2020-05
    Author
    Cristian, Rares
    Metadata
    Show full item record
    Abstract
    Computing 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
    URI
    http://hdl.handle.net/1853/63878
    Collections
    • School of Computer Science Undergraduate Research Option Theses [205]
    • Undergraduate Research Option Theses [862]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology