• Linkage

  • Counting paths in convex polygons

    Let’s count non-crossing paths through the all points of a convex polygon. There is a very simple formula for this, \(n2^{n-3}\) undirected paths through an \(n\)-gon, but why? Here’s a simple coloring-based argument that immediately gives this formula.

  • Linkage

  • Comparing distances along lines

    I’ve written here several times about Gilbert tessellations, most recently in last year’s post about cellular automata that naturally generate them. These are polygonal subdivisions of the plane, generated from the tracks of particles moving at the same speed, where the particles start as oppositely-moving pairs with random locations and directions, and continue moving until they crash into the track of another particle. Here’s Wikipedia’s illustration of these things, generated in 2012 by Claudio Rocchini:

  • Linkage

  • Permuted points of interest

    Suppose you have a map, with certain points of interest marked. To avoid cluttering the map with the labels of these points, you want to list the labels in a line down the side of the map, with each point of interest connected to its label by a line segment. Preferably, the line segments should not cross each other, as they did when I tried to match the sidebar to the points in this example from Google Maps:

  • Linkage

    • The logic of definite descriptions (\(\mathbb{M}\)). Joel Hamkins wrestles with logical formulations of “the”, indicating that a description uniquely identifies something. If you define a logical operator whose value is the thing identified by its argument, and use it in a context that doesn’t uniquely identify something, does your overall formula still have a truth value? Fortunately(?) the stakes are low: several plausible choices produce logics with the same power as classical logic.
  • Linkage

  • Midsphere facts and fallacies

    Some three-dimensional convex polyhedra have a midsphere, a sphere tangent to all of their edges. More strongly, every three-dimensional convex polyhedron has a combinatorially equivalent form, called a “canonical polyhedron”, that has a midsphere. The literature on midspheres is a little sparse and missing some key facts and counterexamples, so I thought I would collect some of them here.

  • Flipping until you are lost

    Start with any triangulation of a convex polygon, and then repeatedly choose a random diagonal and flip it, replacing the two triangles it borders with two different triangles. Eventually, these random flips will cause your triangulation to be nearly equally likely to be any of the possible triangulations of the polygon. But how long is “eventually”? My student Daniel Frishberg has a new answer, in our preprint “Improved mixing for the convex polygon triangulation flip walk” (arXiv:2207.09972).

subscribe via RSS