UROP_2016
Undergraduate Research Opportunities Program

UROP_2016 is the home page for a research project associated with Florida State University's Undergraduate Research Opportunities Program (UROP), starting in Fall Semester 2016 and concluding in Spring Semester 2017, with the participation of Professor Bryan Quaife, Lukas Bystricky and Michael Schneier.

You can view our original project description.

Initially, we have set up a few milestones, which describe skills and knowledge that we expect all the student researchers to master. Our function will be to challenge the students with the milestone, assist them as they work through it, and then to verify that they have completed it properly.

• the Python milestone;
• the plotting milestone;
• the 1d geometry milestone;
• the 2d geometry milestone;
• the triangles milestone;
• the polygons milestone;
• the K-Means milestone;
• the Voronoi milestone;
• the sampling milestone;
• the Delaunay triangulation milestone;
• the 1D Centroidal Voronoi Tessellation (CVT) milestone;
• the Centroidal Voronoi Tessellation (CVT) milestone;
• the Centroidal Voronoi Tessellation of Florida milestone;
• the Density in a Square milestone;
• the Density in a Circle milestone;
• the Discrete Density milestone;
• the CVT Census milestone;

To learn Python, we recommend that our students go through the Python tutorial offered by CodeAcademy. For some of the other topics, we are creating interactive Jupyter notebooks.

• geometry_1d.ipynb, for the 1D geometry milestone;
• geometry_2d.ipynb, for the 2D geometry milestone;
• triangles.ipynb, for the triangles milestone;
• polygons.ipynb, for the polygons milestone;
• polygon_triangulate.py, a Python function needed by the polgyons notebook.
• kmeans.ipynb, for the K-means milestone;
• ruspini.txt, a text file containing the (X,Y) coordinates of 100 points for the K-means notebook.
• voronoi.ipynb, for the Voronoi milestone;
• sampling.ipynb, for the sampling milestone;
• delaunay.ipynb, for the Delaunay milestone;
• ten_nodes.txt, a text file containing the coordinates of 10 nodes; this file is needed for the Delaunay notebook.
• ten_nodes.png, a plot of the ten nodes.
• ten_tri1.txt, a text file containing the triangulation of 10 nodes; this file is needed for the Delaunay notebook.
• ten_tri1.png, an image file of a triangulation of 10 nodes; this file is needed for the Delaunay notebook.
• ten_tri2.txt, a text file containing the Delaunay triangulation of 10 nodes; this file is needed for the Delaunay notebook.
• ten_tri2.png, an image file of the Delaunay triangulation of 10 nodes; this file is needed for the Delaunay notebook.
• cvt_1d.ipynb, for the 1D CVT milestone;
• cvt.ipynb, for the CVT milestone;
• cvt_florida.ipynb, for the CVT Florida milestone;
• florida_shape.txt, a polygon describing the shape of Florida, for the CVT Florida milestone;
• polygon_contains_point.py, a Python function to test whether a point is inside a polygon.
• density_square.ipynb, for the Density in a Square milestone;
• density_circle.ipynb, for the Density in a Circle milestone;
• density_discrete.ipynb, for the Discrete Density milestone;
• cvt_census.ipynb, for the CVT census milestone;
• florida_census.txt, a text file containing 4245 geographic ID's, populations, longitudes and latitudes.

After the milestones, we expect our student researchers to propose a special topic of interest to them; at this point, our function will be to suggest references and examples, and to help with problems in programming, analysis, or writing. After the research project has been completed, the researchers will participate in a poster presentation sponsored by UROP. Our function will be to help with the selection of topics to be presented, the design of the poster, and practice with the oral presentation that should accompany the poster.

• UROPCVTPoster.pdf, "Computational Geometry in Public Policy"

Reference:

1. Aurenhammer reference,
   Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, September 1991, pages 345-405.
2. Jared Burns reference,
   Jared Burns,
   Centroidal Voronoi Tessellations
3. Marc deBerg, Otfried Cheong, Marc Krevald, Mark Overmars,
   Computational Geometry,
   Springer, 2008,
   ISBN: 978-3-540-77973-5,
   LC: QA448.D38.C65.
4. http:/www.personal.psu.edu/qud2/Res/Pic/gallery3.html
   Qiang Du's research gallery 3.
5. Du, Faber, Gunzburger reference,
   Qiang Du, Vance Faber, Max Gunzburger,
   Centroidal Voronoi Tessellations: Applications and Algorithms,
   SIAM Review,
   Volume 41, Number 4, December 1999, pages 637-676.
6. Florida Congressional Districts from 2010 Census,
   from nationalatlas.gov.
7. Lili Ju, Qiang Du, Max Gunzburger,
   Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations,
   Parallel Computing,
   Volume 28, 2002, pages 1477-1500.
8. Stacy Miller reference,
   Stacy Miller,
   The Problem of Redistricting: the Use of Centroidal Voronoi Diagrams to Build Unbiased Congressional Districts
9. Joseph ORourke,
   Computational Geometry in C,
   Second Edition,
   Cambridge, 1998,
   ISBN: 0521649765,
   LC: QA448.D38.
10. https://www.toptal.com/python/computational-geometry-in-python-from-theory-to-implementation
    Charles Marsh,
    Computational Geometry in Python: From Theory to Application.
11. tyler_reddy.pdf (slides)
    https://www.youtube.com/watch?v=gxNa9BD5CnQ (YouTube presentation)
    Tyler Reddy,
    Veni, Vedi, Voronoi: Attacking Viruses using spherical Voronoi Diagrams in Python.