Fabrizio Frati's Theses & Labs

Fabrizio Frati

Home

Research groups:
  Graph Drawing

Publications:
  By type
  By year
  By topic

Teaching:
  Courses (Italian)
  Theses & Labs


Show all news

Polytopes Representations

    Thesis Outline

    Title Type Contact/Supervisor Status Student(s)
    Polytopes Representations M Fabrizio Frati
    unassigned

    Legenda:
       B = Bachelor (3 year degree)
       M = Master (5 year degree)
       L = Lab (course assignment)

    Thesis Description

    The target is to represent a strictly convex polytope in R³ with integer coordinates in minimum volume.

    The best upper bound is actually exponential in the number of vertices of the skeleton of the polytope.

    The best lower bound is actually polynomial in the number of vertices of the skeleton of the polytope.

    This thesis consists of the following phases:

    1. Bibliographic research on the subjects of polytopes and integer realizations of polytopes.
    2. Proposal of possible approaches and algorithms.
    3. Analytical evaluation of the complexity of the algorithms (if any) or experimental evaluation of a brute-force approach.