-
Mutual nearest neighbors versus closest pairs
In the 1990s I published a series of papers on data structures for closest pairs. As long as you already know how to maintain dynamic sets of objects of some type, and answer nearest-neighbor queries among them, you can also keep track of the closest pair, and this can be used as a subroutine in many other computational geometry algorithms. But it turns out that many of those algorithms can now be simplified and sped up by using mutual nearest neighbors (pairs of objects that are each other’s nearest neighbors) instead of closest pairs.
-
Linkage
Beware the Ides of February.
-
Big convex polyhedra in grids
I recently wrote here about big convex polygons in grids, a problem for which we know very precise answers. This naturally raises the question: what about higher dimensions? How many vertices can be part of a convex polyhedron in an grid, or more generally a convex polytope in a -dimensional grid of side length ? Here we do still know some pretty good answers, at least up to constant factors in spaces of constant dimension.
-
Linkage
As usual, follow me on Mathstodon to see these as I post them rather than two weeks later.
-
Simplifying task-milestone diagrams
In my graph algorithms class last week, I covered critical path scheduling, as motivation for the linear-time algorithms for computing shortest and longest paths in directed acyclic graphs. In this scheduling problem, you are given a system of tasks, each with a predicted time to perform it, and constraints that some tasks should be done before others. Assuming that you have enough people working together to perform tasks in parallel, how quickly can you get everything done?
-
Orientations of infinite graphs
An orientation of an undirected graph is the directed graph that you get by assigning a direction to each edge. Several kinds of orientations have been studied. For instance, in a graph with even vertex degrees, an Eulerian orientation makes the numbers of incoming and outgoing degrees equal at each vertex. In a bridgeless graph, a strong orientation makes the resulting directed graph strongly connected. In finite connected graphs, every Eulerian orientation is strong, but that is untrue in infinite graphs. Consider, for instance, the graph of unit distances on the integers, which is Eulerian (every vertex has degree two) but has no strong orientation (every edge is a bridge). Even when a strong orientation exists, an Eulerian orientation might not be strong: the graph of distance-1 and distance-2 integers, with the orientation from smaller to larger numbers, is Eulerian but not strong. So when does an Eulerian strong orientation exist? The answer turns out to be: whenever the obvious obstacles are not present. Every bridgeless connected even-degree infinite graph has an Eulerian strong orientation.
-
Linkage
For the new year, I’ve decided to try to get back into taking photos more frequently, and to make it lower-overhead I’m making individual Mastodon posts for some of them rather than writing a longer blog post for every batch of photos. So that’s why you see a couple of those images inline here.
-
Linkage for the end of the year
- LaTeX, the game (, via). It should be an even higher level to get the commutative diagram to format in Wikipedia’s lobotomized version of LaTeX.
-
Motorcycle graphs and the eventual fate of sparse Life
The motorcycle graph is a geometric structure devised by Jeff Erickson as a simplified model for the behavior of straight skeletons, motivated by the light cycle game in the movie Tron. Its initial data consists of a set of points in the plane (the motorcycles), each with an initial velocity. The motorcycles leave a trail behind them as they move, and a motorcycle crashes (stopping the growth of its trail) when it hits the trail of another motorcycle.
-
Circles crossing at equal angles
Let , , , and be four circles, with pairs , , , and crossing at equal angles (and no crossings among the other two pairs). Then it turns out that the two curvy quadrilaterals forming the inside and outside boundaries of the union of disks each have a circle through their four vertices:
subscribe via RSS