SoCG day 1

I'm in Rio (my first visit to South America!) for the annual Symposium on Computational Geometry.

Your out-of-context quote of the day:

"I don't care about geometry." — Jeff Erickson

(as part of a nice talk exactly characterizing the three-dimensional manifolds-with-quadmeshed-boundary that can be partitioned into a mesh of topological hexahedra).

I think my favorite talk of the day was the first one, by Raimund Seidel, on exact exponential-time algorithms in computational geometry. Raimund was looking at the problem of counting the number of triangulations of a point set (not known to be \( \mathsf{\#P} \)-hard, but not previously known to be solvable faster than listing them all). He showed that it could be solved by a simple and implementable algorithm with running time \( O(2^n n^2), \) by building a DAG in which the vertices represent monotone polygonal chains that could be part of a triangulation, and the edges represent one chain being above another, and differing from it by a single triangle, and then counting paths in this graph.

Another talk I quite enjoyed was by Elyot Grant, who pulled off the rare trick of making me interested in a topic I didn't think I would be interested in: compressive sensing of images. The idea is to reconstruct sparse image data (here sparse means few nonzero pixels, like for instance photos of star fields) using optical equipment that scrambles the image before sensing it, and using many fewer pixel sensors that you would need without the scrambling. If you could scramble the pixels of the image to pixels of the sensor completely at random, it would work well, but then your scrambling device would need to be as complicated as the larger sensor array that you're trying to avoid, so that's no good. Instead, Grant and his coauthor Piotr Indyk showed that a simpler geometric scrambling method based on cutting the image into squares, linearly distorting each square, and then overlaying them all on top of each other is good enough. So far I think he's a strong candidate for the best student presentation award, but this is from a sample of about 1/4 of the student presentations so it may not mean much yet.

SoCG has an unusual organization this year in which the morning consists of SoCG talks and the afternoons consist of several parallel satellite workshops. I haven't seen the numbers yet but to confirm that it's a success, but I like it: it gives me a bigger selection of topics to learn about and, I think, a bigger collection of people interested in geometry all in one place.

Comments: