SoCG paper

As Sariel already noted the SoCG notification is out (couldn't find a list of accepted papers).

I was lucky to get a paper accepted. The paper is on visibility testing in the plane and it's together with Pat Morin.

In the paper we consider query versions of visibility testing and visibility counting. That is, let S be a set of n disjoint line segments in the plane and let s be an element of S. Visibility testing is to preprocess S so that we can quickly determine if s is visible from a query point q. The counting version involves preprocessing S so that one can quickly estimate the number of segments in S visible from a query point q.

The key idea is that one can cover the visibility polygon of a segment with only an expected linear number of triangles (even though its complexity may be quartic), and for all the segments with a quadratic number of triangles, such that given a query point q the number of triangles stabbed is a 2-approximation of the number of segments q can see. Pretty nifty, eh?