Monday, February 15, 2010

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?

Friday, February 12, 2010

JoCG first publications!

I'm sure some of you are wondering what's happening with JoCG (Journal of Computational Geometry). The first papers were published yesterday!

The first paper of JoCG is a Welcome from the Editors-in-Chief by Ken Clarkson and Günter Rote. And the first contribution to be published is: Happy Endings for Flip Graphs by David Eppstein.

So far JoCG has received 21 submissions. Of these, 1 has been accepted and published, 4 have been accepted pending (various levels of) revisions, 8 have been rejected, and the remaining 8 papers are still being reviewed.

All in all, I think it's a good start of the journal. Hopefully it will get even more submissions now when papers are getting published.