Back

Low crossing numbers: https://discrete-notes.github.io/crossing-number,
blog post on a SoCG 21 paper by Mónika Csikós and Nabil H. Mustafa, https://doi.org/10.4230/LIPIcs.SoCG.2021.28

Given points and a family of shapes containing subsets of them, the goal is to connect the points by a matching, path, or spanning tree so that no shape has its boundary crossed by many edges. Many geometric set families have these structures and this paper shows how to find it faster than was previously known.