# CCCG acceptances

The list of accepted papers for CCCG 2013 (the 25th Canadian Conference on Computational Geometry) is now online. I have two papers there, one of which is on the arXiv. (Since the CCCG proceedings will be online eventually, my coauthors didn't see the point in putting the other one up early.)

"Set-Difference Range Queries" (with Mike Goodrich and Joe Simons, arXiv:1306.3482) is about data structures for keeping track of multiple point sets in the same geometric space, and determining how two sets differ within some region of the space. The basic idea is to combine the spatial decompositions commonly used for range searching with sketches of the data associated with each node of the decomposition; one of the sketches we use is the invertible Bloom filter from my work with Mike at WADS'07.

"Universal Point Sets for Planar Graph Drawings with Circular Arcs" (with Patrizio Angelini, Fabrizio Frati, Michael Kaufmann, Silvain Lazard, Tamara Mchedlidze, Monique Teillaud and Alexander Wolff) is about universal point sets, sets of points in the plane that can be used as the vertices for planar drawings of all possible *n*-vertex planar graphs. For drawings in which the edges are straight line segments, universal point sets generally have to have more than *n* points, and determining how many points are needed is a big open problem. But one can also consider universal point sets for other drawing styles; for instance, it was known that every strictly convex curve in the plane contains a set of *n* points that is universal for drawings in which each edge is drawn as a polyline with at most one bend. These polylines could be approximated by hyperbolic arcs, giving a drawing with very simple smooth curves for each edge, but maybe one could use curves that are even more restricted. In this paper we show that this is true for circular arcs: a certain set of *n* points on a parabola is universal for circular-arc drawings of planar graphs. It's purely a theoretical result, though, as the vertices are too unevenly spaced and the edges too tightly packed into a neighborhood of the parabola for these drawings to be useful as visualizations.