Profile cover photo
Profile photo
David Eppstein
David's posts

Post has shared content
Picturing Math: Selections from the Department of Drawings and Prints| Metropolitan Museum of Art| Exhibition

"In 2015, the Metropolitan Museum of Art acquired a series of prints of the most beautiful equations, as drawn by 10 prominent mathematicians and scientists. Mathematician Stephen Smale, for example, chose the relatively simplified numerical analysis equation known as Newton’s Method, first published in the 17th century, while theoretical physicist Steven Weinberg’s demonstration of the Lagrangian of the Electroweak Theory, which contributed to his 1979 Nobel Prize, flows over four dense lines. The 10 prints of mathematical expressions known as the Concinnitas portfolio are the core of Picturing Math: Selections from the Department of Drawings and Prints, currently on view in the Met’s Robert Wood Johnson, Jr. Gallery."

Direct link to the exhibition overview

Post has attachment
Triangle centers as fine art

Post has shared content
The Dirac belt trick

I’ve known about the Dirac belt trick for years, and I often did the Balinese cup trick with my favourite drink, which happens to be beer. I sometimes wondered, can you do the Balinese cup trick with some kind of mechanical device. Last week I was staring at the animation on the Wikipedia page:
Although I was determined focus on another project, I was seduced into building a mechanical model of this thing.
The animation here is a re-glued version of a failed attempt, so it is a bit messy, but it works.

I find it fascinating that you can rotate something by an infinite angle, without net twisting its connection to solid earth. On the animation, note the red tape around one arm. It rotates 360 degrees, while the cube with the Dirac portraits rotates 720 degrees. This is all related to the SU(2) thing being the double cover of our familiar rotation group SO(3). That’s described in a lot of web pages already.
I want to make an animation of a Dirac wave packet, but when…

Animated Photo

Post has shared content
Two new papers describing significant and deeply technical breakthroughs on problems I've worked on. Both of these papers are going to take me some time to digest, but the advertised results are really exciting!

Radoslav Fulek and Jan Kynčl. Hanani-Tutte for approximating maps of graphs. A straight-line drawing of a graph G = (V,E) into the plane is specified by a function f:V→R² assigning (x,y) coordinates to each vertex; the edges are of G are drawn as straight line segments. A straight-line drawing is an embedding if all vertices are disjoint and all edges are interior-disjoint. Finally, a straight-line drawing f is a weak embedding if it is arbitrarily close to an embedding; that is, for any ε>0, there is an embedding g such that d(f(v),g(v))<ε for every vertex v. (Pick your favorite metric; it doesn't matter.) In other words, a weak embedding is the limit of an infinite sequence of embeddings. Fulek and Kynčl describe the first polynomial-time algorithm to decide whether a given straight-line drawing of a given planar graph is a weak embedding. (I have a couple of papers developing fast algorithms for the special case of weakly simple polygons, where the underlying graph G is a cycle.) Their proof uses subtle tools from algebraic topology (van Kampen obstructions) that generalize the Hanani-Tutte theorem (or more properly, the Flores-van Kampen-Hannai-Tutte-Shapiro-Wu Theorem): A graph is planar if and only if it can be drawn in the plane so that every pair of independent edges crosses an even number of times.

Daniel Kane, Shachar Lovett, and Shay Moran. Near-optimal linear decision trees for k-SUM and related problems. The 3SUM problem asks, given a bag of n real numbers, whether any three of them sum to zero. There is a natural algorithm to solve this problem in O(n^{(k+1)/2}) time when k is odd and O(n^{k/2}log n) time when k is even, and it is a long-standing open problem to significantly improve these bounds, even for the special case k=3. In my PhD thesis, I proved that these bounds are tight (except for the log factor when k is even) in the so-called k-linear decision tree model. This is a generalization of the comparison tree model, where instead of comparisons, the algorithm can query the sign of any linear combination of at most three input values. Without the "at most three" restriction, the best lower bound known is only Ω(n log n).
(Ailon and Chazelle later rewrote my proof the right way.) In 2014, Grønlund and Pettie proved that in the 4-linear decision tree model, a classical trick of Fredman implies an upper bound of O(n^{3/2} sqrt{log n}), the root-log factor was quicly removed by Gold and Sharir. Kane, Lovett, and Moran show that 3SUM can be solved in O(n log^2 n) queries in the 6-linear decision tree model. In fact, they derive an O(kn log^2 n) upper bound for kSUM in the 2k-linear decision tree model. Their proof relies on the authors' recent definition of inference dimension, which they previously applied to active classification.

Deep, deep stuff. 

Post has shared content
Punctured surface. Triaxial (Kagome) mesh with heptagons. Woven paper strips follow approximately geodesic paths.

Post has shared content
Rule 135 as architectural decoration
Cambridge North is a brand new train station, and the building’s got a fab bit of cladding with a design ‘derived from John Horton Conway’s “Game of Life” theories which he established while at Gonville and Caius College, Cambridge in 1970.’ One problem:…

Post has attachment
"Exhaustive search of convex pentagons which tile the plane" by Michaël Rao (May 1, 2017). Rao claims to have a computational proof that the 15 known types of monohedral convex pentagon tiles are the only ones possible.

Via +Bob Hearn at

Post has attachment
Combining cuckoo filters with a two-of-three variant of cuckoo hashing from a 2011 paper by Amossen and Pagh leads to a bit-parallel set intersection algorithm that shaves a loglog factor from previous methods.

Post has shared content
Amusingly acted and not-too-technical video about Frechet distances between one-dimensional trajectories

Post has attachment
Tories use child porn and terrorism as an excuse to censor political speech on the British internet. "[Tech companies] would be forced to help controversial government schemes like its Prevent strategy, by promoting counter-extremist narratives. ... The Conservatives will also seek to regulate the kind of news that is posted online ... If elected, Theresa May will 'take steps to protect the reliability and objectivity of information that is essential to our democracy.'"
Wait while more posts are being loaded