Paper is available as open access; you can watch the conference talk on YouTube. Jonathan Klawitter & Felix Klesen & Joris Y. Scholl & Thomas C. van Dijk & Alexander Zaft. The 12th International Conference on Geographic Information Science. (2023) Abstract. A geophylogeny is a phylogenetic tree where each leaf (biological taxon) has an associated geographic location (site). To clearly visualize a geophylogeny, the tree is typically represented as a crossing-free drawing next to a map.…

(You can watch the video version of this post on YouTube.) Now when we talk about an optimisation problem, right, there’s actually different variants that we’re not usually explicit about. What is, say, the independent set problem? INDEPENDENT SET (CONSTRUCTION) GIVEN: a graph G QUESTION: what is the largest independent set in G? INDEPENDENT SET (OPTIMISATION) GIVEN: a graph G QUESTION: what is the size of the largest independent set in $G$?…

How does a typical C++ standard library implement std::sort? The standard does not actually mandate a particular algorithm, but when I last looked at my installation (around 2020), I found something called introsort and this seems to be a common choice. The name stands for “introspective” sort – it pays attention to how it is doing – and it was intro-duced (haha) in a 1997 paper by David Musser.1 The code also seemed to call __adjust_heap (heapsort?…

(You can watch the video version of this post on YouTube.) Now I’m aware I already have a number of posts on here being pedantic about NP-hardness and, uh, let’s do another one of those! We’ve alreay seen a version of the SUM OF RADICALS problem, where it turned out comparing sums of square roots is tricky. But irrational numbers are kind of wild, right, so maybe that shouldn’t really be a surprise and surely it’s a bit of a niche concern: irrational numbers?…

(You can watch the video version of this post on YouTube.) Now there is a well-developed theory of affine transformations with Cartesian coordinates – homogeneous coordinates, actually – by multiplying vectors and matrices (that’s fine), but here are some special cases that are handy to have at the ready. First of all: if you rotate the vector $(x,y)$ by 90 degrees counterclockwise, then you get $(-y, x)$. If you multiply out the appropriate rotation matrix, this is also what you get, of course, but it keeps things simple to know that it’s really just a swizzle and a minus sign.…