-
Linkage
Still at home, hoping the coffee arrives tomorrow as scheduled.
-
Backyard sunlight
A few photos from my garden:
-
UCI Ecological Preserve
The UCI Ecological Preserve is a 60-acre patch of coastal sage scrub, adjoining the housing complex in which I live.
-
Stay-at-home linkage
Looks like we’ll all be seeing a long time at home with little to do but go online. So here is my usual update of links I recently found interesting. (I’m deliberately not linking Coronavirus information, despite its importance, both because I’m not an expert and have neither useful original opinions to contribute nor adequate filters between information and misinformation, and because I suspect that many people’s mental health depends on not getting overloaded with that stuff while there’s so little to do but staying isolated and avoiding becoming part of the problem).
-
More on uniqueness in Sudoku
My first post on this blog, lo these nearly 15 years ago, discussed a program I had written to try to solve Sudoku puzzles deductively (rather than by the easier computational method, backtracking), with the goal of being able to automatically grade the puzzles and automatically generate explanations for how to solve a given puzzle. And a few months later I posted again, on deduction rules that take advantage of the assumption that a puzzle has a unique solution, by ruling out choices that would cause any solution consistent with them to become non-unique. Since then, that part of my solver has been relatively stable, although I have added other rules for Nishio and 2SAT and posted here about more general uniqueness deduction rules in map-coloring puzzles.
-
Mathematics books by women
It’s International Women’s Day, and The Aperiodical has a new piece up on “Books about Maths by Women”. One of my own projects for the last few weeks has been to create Wikipedia articles on noteworthy mathematics books, and so far roughly half of the creations have included at least one woman among their authors. They are (alphabetical by title):
-
Leap day linkage
- Jeff Erickson links 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).
-
Two applications of maximum matching
This quarter I’m teaching a course on graph algorithms (an upper-division elective, so only around 200 students; our required classes are much bigger) and we’ve reached the part of the course where we discuss matching. Motivating bipartite matching, perfect matching, weighted matching, and stable matching are all easy enough but I wanted a few more examples of applications of non-bipartite maximum-cardinality matching, so I asked my colleague Vijay Vazirani who responded with two cute ones that I wasn’t already familiar with.
-
Snowflake spanners
My previous post gave an example of a largish random point set where the greedy geometric spanner for distance ratio 2 had no crossings, while the spanner for the lower distance ratio had many (linearly many) crossings. And you might think from that example that there is some threshold for which distance ratios above the threshold always have planar greedy spanners, or even that the threshold is at or below 2. But it’s not true.
-
Spanners have sparse crossings
In a 2017 SIGSPATIAL paper with Sid Gupta, Sid and I modeled non-planar road networks as graph drawings whose edges intersect sparsely, and showed that this implies that these graphs have small separators, allowing algorithms designed for planar graphs (such as linear-time shortest paths) to be extended to them. My latest preprint, with UCI student Hadi Khodabandeh, uses similar ideas of sparse edge intersections to show that greedy geometric spanners also have small separators. The paper is “On the edge crossings of the greedy spanner” (arXiv:2002.05854).
subscribe via RSS