Indira Lara Chatterji has some nice open-licensed animated gifs of concepts in low-dimensional geometry and topology at https://math.unice.fr/~indira/Mygifs.html

This is one of them, unzipping a 2-torus.

@sarielhp Thanks. I'll be sure to add a citation the next time I revise.

New blog post: Spanners have sparse crossings

https://11011110.github.io/blog/2020/02/17/spanners-have-sparse.html

One of the first non-trivial straight skeletons (as a roof model), from _Kotirte Ebenen (Kotirte Projektionen) und deren Anwendung_ by Gustav A. von Peschka (1877). See https://en.wikipedia.org/wiki/Straight_skeleton

The world's hardest irregular sudoku: https://puzzling.stackexchange.com/questions/93766/your-task-is-to-create-the-worlds-hardest-irregular-sudoku

The joke is that the puzzle itself is easy. "Hardest" means only that it has few givens. The meta-puzzle is to construct the puzzle: a 9x9 grid divided into 9 9-ominoes (analogous to the 3x3 blogs of standard sudoku), with as few grid cells as possible specified as givens so that there is a unique solution.

A quasi-polynomial algorithm for well-spaced hyperbolic TSP: https://arxiv.org/abs/2002.05414

This new preprint by Sándor Kisfaludi-Bak (accepted to SoCG) just came out and caught my attention. TSP is NP-hard for Euclidean points or close-together hyperbolic points. This paper shows that it's much easier when the points are widely spaced in the hyperbolic plane. The idea is to separate the input by a short line segment that the solution crosses few times and apply dynamic programming.

Jorge Hirsch repudiates the h-index he invented: https://arxiv.org/abs/2001.09496

"I have now come to believe that it can also fail spectacularly and have severe unintended negative consequences. I can understand how the sorcerer’s apprentice must have felt."

(This is an aside; the actual article is about Hirsch's difficulty in breaching the orthodox consensus on superconductivity.)

How to generate all flats of the cycle matroid of a graph: https://mathoverflow.net/a/350526/440

A flat is a partition of vertices into connected induced subgraphs. If you give edges distinct weights and look at the minimum spanning forests of the flats, you get a nice tree structure on the space of all flats where the parent of a flat removes the heaviest edge from its forest (partitioning one tree and therefore one subgraph into two). This leads to efficient enumeration algorithms using reverse search.

The list of accepted papers for this year's Symposium on Computational Geometry (late June in Zürich) is online: https://socg20.inf.ethz.ch/socg-accepted

So far there are only authors and titles (by the date of the conference the full papers will be online open access) but probably for many of them you can search for the title and find more.

Big cuts to most US research funding agencies in Trump's proposed 2021 budget: https://www.sciencemag.org/news/2020/02/trump-s-2021-budget-drowns-science-agencies-red-ink-again

The only not-so-bad news here is that actual federal budgets have to start in the House of Representatives, not the White House. But this is probably a warning of budget battles to come soon.

Visualize how much junk from third-party sites you download when you visit your favorite web site: https://simonhearne.com/2015/find-third-party-assets/

Mathstodon.xyz: Completely clean. Wikipedia: only a few small bits and pieces from other Wikimedia sites. Some other sites that I visit regularly: lots of junk. Adblockers help, but attention to keeping things slim in site design would help more.

Triangle dissection, no shared edges: https://math.stackexchange.com/questions/1819928/triangle-dissection-no-shared-edges

(the intended target of a recent broken link from mathpuzzle.com)

The question is how to divide a triangle into smaller triangles, no two sharing a whole edge, but the solutions shown also have no separating triangles and a straight angle at each interior vertex. Double-counting angles and combining with Euler shows that, with these conditions, \(F=V-1\). Do all internally-4-connected planar graphs with \(F=V-1\) work?

@JordiGH Maybe the extroverts are all on that other more-widely-used microblogging site?

Schnittpunkte: https://www.walser-h-m.ch/hans/Schnittpunkte/

Hans Walser extends his book 99 Points of Intersection (https://en.wikipedia.org/wiki/99_Points_of_Intersection) to over 800 geometric constructions involving points where three or more lines, circles, or other curves all cross each other.

The text is in German but that doesn't matter because there's so little of it. Most of the content is a figure for each point of intersection, with three smaller figures showing its construction.

- Home page
- https://www.ics.uci.edu/~eppstein/

I'm a computer scientist at the University of California, Irvine, interested in algorithms, data structures, discrete geometry, and graph theory.

Joined Apr 2017