Click on the associated figure to download the PDF version of the paper. Most of this work is supported by the National Science Foundation, with additional funding by DARPA, the Mellon Foundation, and the Whiting Fellowship. Any opinions, findings, and conclusions are those of the author(s) and do not necessarily reflect the views of these organizations.
DIScrete and Computational Geometry
Princeton University Press (2011) with Joe O’Rourke (Smith)
This book covers traditional topics such as convex hulls, triangulations, and Voronoi diagrams, as well as more recent subjects like pseudotriangulations, curve reconstruction, and locked chains. It also touches on more advanced material, including Dehn invariants, associahedra, quasigeodesics, Morse theory, and the recent resolution of the Poincaré conjecture. Connections to real-world applications are made throughout, and algorithms are presented independently of any programming language, along with numerous exercises and unsolved problems.
A MATH PROBLEM FOR PI DAY
The Washington Post, Opinion Editorial (March 14, 2018)
Today's dominant narrative casts mathematics and the sciences as stewards of difficult ideas, with the humanities and arts relegated to the simpler struggles. This assumption is not only flawed but also completely backward, for there is a missing part to this story: the hidden dimension of complexity.
Geometric Realizations of the 3D AssociahedrON
Symposium on Computational Geometry: Multimedia (2018)
D. Johnson (Harvey Mudd), J. Lee (Boston University), J. Warley (UMass, Amherst)
The associahedron is a convex polytope whose 1-skeleton is isomorphic to the flip graph of a convex polygon. There exists an elegant geometric realization of the associahedron, using the remarkable theory of secondary polytopes, based on the geometry of the underlying polygon. We present an interactive application that visualizes this correspondence in the 3D case.
STAR UNFOLDING OF BOXES
Symposium on Computational Geometry: Multimedia (2018)
Y X. Hong (Pomona) , D. Demas (Amazon)
Given a convex polyhedron, the star unfolding of its surface is obtained by cutting along the shortest paths from a fixed source point to each of its vertices. We present an interactive application that visualizes the star unfolding of a box, such that its dimensions and source point locations can be continuously toggled by the user.
Cartography of Tree spacE
MIT Leonardo Journal 52 (2019)
O. Schuh (Philadelphia artist)
How can vibrant, contemporary art be produced that deals with vibrant, contemporary mathematics? To address this, a collaboration began between an artist and a mathematician, revolving around recent problems in phylogenetics and the space of evolutionary trees. The result was two-fold: First, a triptych of paintings was created, using acrylic, graphite, watercolor, and metal leaf, that focused on different navigations within this tree space. And second, a novel set of open mathematics problems was discovered solely from this investigation.
A Space of phylogenetic Networks
SIAM Journal on Applied Algebra and Geometry 1 (2017) 683-705
S. Petti (Georgia Tech)
A classic problem in computational biology is constructing a phylogenetic tree given a set of distances between n species. In most cases, a tree structure is too constraining. We consider a circular split network, a generalization of a tree in which multiple parallel edges signify divergence. A geometric space of such networks is introduced, forming a natural extension of the work by Billera, Holmes, and Vogtmann on tree space. We explore properties of this space, and show a natural embedding of the compactification of the real moduli space of curves within it.
Visualizing Scissors Congruence
Symposium on Computational Geometry: Multimedia (2016)
Z. Epstein, D. Smirnov (Pomona)
Consider two simple polygons with equal area. The Wallace-Bolyai-Gerwien theorem states that these polygons are scissors congruent, able to be dissected into finitely many congruent polygonal pieces. We present an interactive application that visualizes this constructive proof.
Navigation in Tree Spaces
Advances in Applied Mathematics 67 (2015) 75 - 95
J. Morava (Johns Hopkins)
The orientable cover of the moduli space of real genus zero algebraic curves with marked points is a compact aspherical manifold tiled by associahedra, which resolves the singularities of the space of phylogenetic trees. The resolution maps planar metric trees to their underlying abstract representatives, collapsing and folding an explicit geometric decomposition of the moduli space into cubes. This decomposition endows the resolving space with an interesting canonical pseudometric.
Convex Polytopes from Nested Posets
European Journal of Combinatorics 43 (2015) 229 - 248
S. Forcey, S. Reisdorf, P. Showers (Akron)
Motivated by the graph associahedron KG, a polytope whose face poset is based on connected subgraphs of G, we consider the notion of associativity and tubes on posets. This leads to a new family of simple convex polytopes obtained by iterated truncations. These generalize graph associahedra and nestohedra, even encompassing notions of nestings on CW-complexes, but fall in a different category altogether than generalized permutohedra.
Polyhedral Covers of Tree Space
SIAM Journal of Discrete Mathematics 28 (2014) 1508 - 1514
D. Huang (Cornell), D. Spadacene (Michigan)
We construct the space of phylogenetic trees from local gluings of classical polytopes, the associahedron and the permutohedron. Its homotopy is also reinterpreted and calculated based on polytope data.
Skeletal Configurations of Ribbon Trees
Discrete Applied Mathematics 170 (2014) 46 - 54
H. Cheng (Arizona), B. Li (NIH), A. Risteski (Princeton)
The straight skeleton construction creates a straight-line tree from a polygon. Motivated by moduli spaces from algebraic geometry, we consider the inverse problem of constructing a polygon whose straight skeleton is a given tree. We prove there exists only a finite set of planar embeddings of a tree appearing as straight skeletons of convex polygons. The heavy lifting of this result is performed by using an analogous version of Cauchy's arm lemma. Computational issues are also considered, uncovering ties to a much older angle bisector problem
Diagonalizing the Genome II: Toward Possible Applications
arxiv preprint 2012
J. Morava (Johns Hopkins)
We construct a related (stacky) resolution of a space of real quadratic forms, and suggest, perhaps without much justification, that systems of oscillators parametrized by such objects may may provide useful models in genomics.
The Shape of Associativity
Canadian Mathematical Society Notes 44 (2012) 12 - 14
Associativity is ubiquitous in mathematics. Unlike commutativity, its more popular cousin, associativity has for the most part taken a backseat in importance. But over the past few decades, this concept has blossomed and matured. We start with a brief look at three fields of mathematics where this has transpired, and then explore the visualization of associativity.
Deformations of Associahedra and Visibility Graphs
Contributions to Discrete Mathematics 7 (2012) 68 - 81
R. Shah (Williams), X. Shao (MIT), E. Winston (Bard)
Given a arbitrary polygon P with holes, we construct a polytopal complex analogous to the associahedron based on convex diagonalizations of P. This polytopal complex is shown to be contractible, and a geometric realization is provided based on the theory of secondary polytopes. We then reformulate a combinatorial deformation theory and present an open problem based on visibility which is a close cousin to the carpenter's rule statement of computational geometry.
What makes a Tree a Straight Skeleton?
Proceedings of the Canadian Conference on Computational Geometry (2012)
O. Aichholzer (Graz), H. Cheng (Arizona), T. Hackl (Graz), S. Huber (Salzburg), B. Li (Williams), A. Risteski (Princeton)
Let G be a cycle-free connected straight-line graph with predefined edge lengths and fixed order of incident edges around each vertex. We address the problem of deciding whether there exists a simple polygon P such that G is the straight skeleton of P. We show that for given G, such a polygon P might not exist, and if it exists it might not be unique.
Moduli Spaces of Punctured Poincaré Disks
Tamari Memorial Festschrift: Progress in Mathematics Volume 299 (2012)
B. Fehrman (Chicago), T. Heath (Columbia), A. Vashist (Michigan)
The Tamari lattice and the associahedron provide methods of measuring associativity on a line. The real moduli space of marked curves captures the space of such associativity. We consider a natural generalization by considering the moduli space of marked particles on the Poincaré disk, extending Tamari's notion of associativity based on nesting. A geometric and combinatorial construction of this space is provided, which appears in Kontsevich's deformation quantization, Voronov's swiss-cheese operad, and Kajiura and Stasheff's open-closed string theory.
Esopus Magazine (Fall 2011)
A.Shotz (artist), P. Natarajan (Yale)
An artist, a mathematician, and a cosmologist walk into a bar, and discuss the nature of infinity.
Journal of Combinatorial Theory, Series A 118 (2011) 2035 - 2055
M. Carr (Brandeis), S. Forcey (Tennessee State)
Given a simple graph G, the graph associahedron KG is a simple polytope whose face poset is based on the connected subgraphs of G. This paper defines and constructs graph associahedra in a general context, for pseudographs with loops and multiple edges, which are also allowed to be disconnected. We then consider deformations of pseudograph associahedra as their underlying graphs are altered by edge contractions and edge deletions.
Deformations of Bordered Surfaces and Convex Polytopes
Notices of the American Mathematical Society 58 (2011) 530 - 541
T. Heath (Columbia), C. Vipismakul (UT Austin)
We consider the moduli space of Riemann surfaces with boundary and marked points. Such spaces appear in open-closed string theory, particularly with respect to holomorphic curves with Lagrangian submanifolds. We consider a combinatorial framework to view the compactification of this space based on the pair-of-pants decomposition of the surface, relating it to the well-known phenomenon of bubbling. Our main result classifies all such spaces that can be realized as convex polytopes.
Particle Configurations and Coxeter Operads
Homotopy and Related Structures 4 (2009) 83 - 109
S. Armstrong (Williams), M. Carr (Michigan), E. Engler (Williams), A. Leininger (MIT), M. Manapat (Berkeley)
There exist natural generalizations of the real moduli space of Riemann spheres based on manipulations of Coxeter complexes. These novel spaces inherit a tiling by the graph-associahedra convex polytopes. We obtain explicit configuration space models for the classical infinite families of finite and affine Weyl groups using particles on lines and circles. A Fulton-MacPherson compactification of these spaces is described, which in then used to define the Coxeter operad. A complete classification of the building sets of these complexes is also given, along with a computation of their Euler characteristics.
Shape Deformation in Continuous Map Generalization
GeoInformatica 13 (2009) 203 - 221
J. Danciger (Stanford), J. Mugno (Maryland), D. Sheehy (Carnegie Mellon), R. Ward (Princeton)
Given a collection of regions on a map, we seek a method of continuously altering the regions as the scale is varied. This is formalized and brought to rigor as well-defined problems in homotopic deformation. We ask the regions to preserve topology, area-ratios, and relative position as they change over time. A solution is presented using differential methods and computational geometric techniques. Most notably, an application of this method is used to provide an algorithm to obtain cartograms.
A Realization of Graph Associahedra
Discrete Mathematics 309 (2009) 271 - 276
Given any finite graph, we offer a simple realization of its corresponding graph associahedron polytope using integer coordinates.
Marked Tubes and the Graph Multiplihedron
Algebraic and Geometric Topology 8 (2008) 2081 - 2108
S. Forcey (Tennessee State)
Given a graph G, we construct a convex polytope whose face poset is based on marked subgraphs of G. Not only does this yield a natural generalization of the multiphihedron, but features of this polytope appear in works related to quilted disks, bordered Riemann surfaces, and operadic structures. Certain examples of graph multiplihedra are related to Minkowski sums of simplices and cubes and others to the permutohedron.
Juggling Braids and Links
The Mathematical Intelligencer (2007) 15 - 22
J. Mugno (Maryland)
Using a simplistic model of juggling based on physics, a natural map is constructed from the set of periodic juggling patterns to links. We then show that all topological links can be juggled.
Compatible Triangulations and Point Partitions by Series-Triangular Graphs
Computational Geometry: Theory and Applications 34 (2006) 195 - 202
J. Danciger (UC Santa Barbara), D. Sheehy (Princeton)
We introduce series-triangular graph embeddings and show how to partition point sets with them. This result is then used to prove an upper bound on the number of Steiner points needed to obtain compatible triangulations of point sets. The problem is generalized to finding compatible triangulations for more than two point sets and we show that such triangulations can be constructed with only a linear number of Steiner points added to each point set.
Coxeter Complexes and Graph Associahedra
Topology and its Applications 153 (2006) 2155 - 2168
M. Carr (Michigan)
Given a graph G, we construct a simple, convex polytope whose face poset is based on the connected subgraphs of G. This provides a natural generalization of the Stasheff associahedron and the Bott-Taubes cyclohedron. Moreover, we show that for any simplicial Coxeter system, the minimal blow-ups of its associated Coxeter complex has a tiling by graph associahedra. These spaces are natural generalizations of the Deligne-Knudsen-Mumford compactification of the real moduli space of curves.
Continuous Foldability of Polygonal Paper
Proceedings of the Canadian Conference on Computational Geometry (2004)
E. Demaine (MIT), J. Mitchell (Stony Brook), J. O'Rourke (Smith)
We prove that any given well-behaved folded state of a piece of paper can be reached via a continuous folding process starting from the unfolded paper and ending with the folded state.
Combinatorial Equivalence of Real Moduli Spaces
Notices of the American Mathematical Society 51 (2004) 620 - 628
The Riemann moduli space of spheres with marked points has become a central object in mathematical physics. There is a Deligne-Knudsen-Mumford compactification of this space coming from Geometric Invariant Theory which allows collisions of points of the configuration space. The real spaces, unlike their complex counterparts, have an inherent tiling, which allows an intuitive, combinatorial construction. Along the way, we provide a new construction of the associahedron from products of simplices.
A Space of Cyclohedra
Discrete and Computational Geometry 29 (2003) 61 - 75
The real points of the Deligne-Knudsen-Mumford moduli space of marked points on the sphere have a natural tiling by associahedra. We extend this idea to construct an aspherical space tiled by cyclohedra. We explore the structure of this space, coming from blow-ups of hyperplane arrangements, as well as discuss possibilities of its role in knot theory and mathematical physics.
Cellular Structures determined by Polygons and Trees
Annals of Combinatorics 5 (2001) 71 - 98
R. C. Read (Waterloo)
The polytope structure of the associahedron is decomposed into two categories, types and classes. The classification of types is related to integer partitions, whereas the classes present a new combinatorial problem. We solve this, and incorporate the results into properties of moduli spaces. Connections are discussed with relation to classic combinatorial problems as well as to other sciences.
Tessellations of Moduli Spaces and the Mosaic Operad
Contemporary Mathematics 239 (1999) 91 - 114
We construct a new (cyclic) operad of mosaics defined by polygons with marked diagonals. Its underlying (aspherical) spaces are the compactification of the real moduli space of curves, naturally tiled by Stasheff associahedra. We describe them as iterated blow-ups and show that their fundamental groups form an operad with similarities to the operad of braid groups.