Some recent CG related cfp:
- Symposium on Computational Geometry (SoCG'11) will be held on June 13-15 in Paris, France. Deadline: Dec 1
There is also a CG Learning Summer School (June 9-11) as a satellite event.
- European Workshop on Computational Geometry (EuroCG'11) will be held on March 28-30, 2011, in Morschach, Switzerland. Deadline: Jan 9
- Conference on Geosensor Networks (GSN'11) will be held on July 11-13, 2011, in Melbourne, Australia. Deadline: Mar 4
Tuesday, October 19, 2010
Wednesday, June 30, 2010
Some SoCG'10 papers
SoCG is over for this year. In general I thought that the quality of the accepted papers was very high, and I really enjoyed many of the presentations and the results. There has already been numerous reports from SoCG (Sorelle I, II and III, David, Sariel and Suresh), and below I'm just going to briefly mention three of the ones that I found the most interesting - in order of presentation.
Timothy Chan - Optimal Partition Trees (Paper).
Timothy improves on a result from 1992 by Matousek. He presents a simpler construction with a better preprocessing time. There are already numerous blog comments on it (Sariel and Sorelle).
Joe Mitchell - A constant factor approximation algorithm for TSP with neighbourhoods in the plane (paper).
This is a problem I've been working on back and forth for a long time. Given a collection of objects (usually polygons) in the plane, called neighbourhoods, find the shortest tour that visits all neighbourhoods. In 2002 we presented a constant factor approximation algorithm for fat disjoint objects of arbitrary size. This was the first constant factor approximation algorithm for arbitrary size objects. Joe has several results on the topic and in his SoCG paper he presents the first constant-factor approximation algorithm for TSPN on an arbitrary set of disjoint, connected neighbourhoods in the plane. This has been an open problem since the mid-90's and Joe's paper is a big step forward. Of course, ultimately we would like a constant-factor approximation for the general case, not necessarily disjoint neighbourhoods. He has several interesting general observations in his paper. One is that skinny neighbourhoods are not longer a big problem. Using “directional hulls”, which are fat, for an appropriate choice of one of two coordinate systems. Then one can partition the regions into two sets (“blue” regions and “red” regions). Separately find approximating tours of each set, and then use the Combination Lemma (Arkin and Hassin) to combine into a tour of the entire set.
Anne Driemel, Sariel Har-Peled and Carola Wenk - Approximating the Frechet distance for realistic curves in near linear time (paper).
This is probably my favourite paper at SoCG this year. It's an important problem (imho) and it's great to finally see a subquadratic time algorithm with reasonable assumptions. The aim is to calculate the Frechet distance between two curves. They introduce a notion of k-bounded curvature which means that in a ball of radius r the length of the trajectory inside that ball is bounded by k*r (this family of curves is closed under simplification, a property that is very useful in practice). This sounds like a reasonable assumption for many applications (although not for trajectories generated from football players). They present a (1+eps)-approximation algorithm to compute the Frechet distance between two curves with k-bounded curvature and prove that this can be done in near-linear time. The key idea is that after the curves have been simplified the complexity of the reachable free space is linear for fixed k and epsilon (the free space diagram is the standard tool for computing the Frechet distance between curves but has quadratic complexity).
Timothy Chan - Optimal Partition Trees (Paper).
Timothy improves on a result from 1992 by Matousek. He presents a simpler construction with a better preprocessing time. There are already numerous blog comments on it (Sariel and Sorelle).
Joe Mitchell - A constant factor approximation algorithm for TSP with neighbourhoods in the plane (paper).
This is a problem I've been working on back and forth for a long time. Given a collection of objects (usually polygons) in the plane, called neighbourhoods, find the shortest tour that visits all neighbourhoods. In 2002 we presented a constant factor approximation algorithm for fat disjoint objects of arbitrary size. This was the first constant factor approximation algorithm for arbitrary size objects. Joe has several results on the topic and in his SoCG paper he presents the first constant-factor approximation algorithm for TSPN on an arbitrary set of disjoint, connected neighbourhoods in the plane. This has been an open problem since the mid-90's and Joe's paper is a big step forward. Of course, ultimately we would like a constant-factor approximation for the general case, not necessarily disjoint neighbourhoods. He has several interesting general observations in his paper. One is that skinny neighbourhoods are not longer a big problem. Using “directional hulls”, which are fat, for an appropriate choice of one of two coordinate systems. Then one can partition the regions into two sets (“blue” regions and “red” regions). Separately find approximating tours of each set, and then use the Combination Lemma (Arkin and Hassin) to combine into a tour of the entire set.
Anne Driemel, Sariel Har-Peled and Carola Wenk - Approximating the Frechet distance for realistic curves in near linear time (paper).
This is probably my favourite paper at SoCG this year. It's an important problem (imho) and it's great to finally see a subquadratic time algorithm with reasonable assumptions. The aim is to calculate the Frechet distance between two curves. They introduce a notion of k-bounded curvature which means that in a ball of radius r the length of the trajectory inside that ball is bounded by k*r (this family of curves is closed under simplification, a property that is very useful in practice). This sounds like a reasonable assumption for many applications (although not for trajectories generated from football players). They present a (1+eps)-approximation algorithm to compute the Frechet distance between two curves with k-bounded curvature and prove that this can be done in near-linear time. The key idea is that after the curves have been simplified the complexity of the reachable free space is linear for fixed k and epsilon (the free space diagram is the standard tool for computing the Frechet distance between curves but has quadratic complexity).
Tuesday, June 29, 2010
New position at the university of sydney (algorithmic machine learning)
We have a new position in "algorithmic machine learning" at the university of sydney.
The deadline for submitting an application is 12-august-2010.
The position is at the level of "lecturer" which is the same as an assistant professor, or "senior lecturer" which is again the same as an assistant professor but usually slightly older, with some gray hair, possibly kids, and a mortgage.
The deadline for submitting an application is 12-august-2010.
The position is at the level of "lecturer" which is the same as an assistant professor, or "senior lecturer" which is again the same as an assistant professor but usually slightly older, with some gray hair, possibly kids, and a mortgage.
Monday, June 14, 2010
More JoCG articles
Another two articles published in JoCG (and currently another 16 under review):
On the Stretch Factor of Convex Delaunay Graphs
by Prosenjit Bose, Paz Carmi, Sebastien Collette and Michiel Smid
Visibility Maps of Realistic Terrains have Linear Smoothed Complexity
by Mark de Berg, Herman Haverkort and Constantinos P. Tsirogiannis
Just arrived in Snowbird for SoCG'10. I was hoping for a warm summer weather, instead it's raining and there's still snow around the hotel.
On the Stretch Factor of Convex Delaunay Graphs
by Prosenjit Bose, Paz Carmi, Sebastien Collette and Michiel Smid
Visibility Maps of Realistic Terrains have Linear Smoothed Complexity
by Mark de Berg, Herman Haverkort and Constantinos P. Tsirogiannis
Just arrived in Snowbird for SoCG'10. I was hoping for a warm summer weather, instead it's raining and there's still snow around the hotel.
Tuesday, June 8, 2010
JoCG new article
The second scientific article in JoCG was just published. It's an expository of visibility and blockers by Attila Por and David Wood. Enjoy!
Tuesday, May 25, 2010
CATS 2011 call for papers (the australian theory conference)
CATS 2011 -- Computing: The Australasian Theory Symposium
Perth, Australia, January 17-20, 2011
http://cats.it.usyd.edu.au/
The 17th Computing: The Australasian Theory Symposium (CATS) will be held in Perth, Australia, January 17-20, 2011. CATS is an annual conference held in the Australia-New Zealand region, dedicated to theoretical computer science.
Authors are invited to submit papers that present original and unpublished research on topics including (but not limited to) the following areas: algorithms and data structures, complexity theory, graph theory, graph algorithms and combinatorics, semantics of programming languages, approximation and randomized algorithms, combinatorial optimization, formal program specification and transformation, computational geometry, algorithmic game theory, computational biology, logic and type systems, and computability.
Deadlines and other dates:
Paper submission deadline:Monday August 16, 2010
Acceptance notification:Monday October 4, 2010
Final version of accepted papers due:Monday November 5, 2010
Early registration: Monday December 6, 2010
Conference dates: January 17-20, 2011
The proceedings of this event will be published by the Australian Computer Society (ACS) in the CRPIT Series (http://crpit.com/), and will also appear in the ACM digital library.
CATS 2011 is part of the Australasian Computer Science Week (ACSW), an international annual conference event, supported by the Computing Research and Education Association (CORE) in Australia. ACSW 2011 is hosted by Curtin University in Perth, Australia.
For more information please visit http://cats.it.usyd.edu.au/
Contact: taso viglas (aviglas+cats2011@gmail.com)
Perth, Australia, January 17-20, 2011
http://cats.it.usyd.edu.au/
The 17th Computing: The Australasian Theory Symposium (CATS) will be held in Perth, Australia, January 17-20, 2011. CATS is an annual conference held in the Australia-New Zealand region, dedicated to theoretical computer science.
Authors are invited to submit papers that present original and unpublished research on topics including (but not limited to) the following areas: algorithms and data structures, complexity theory, graph theory, graph algorithms and combinatorics, semantics of programming languages, approximation and randomized algorithms, combinatorial optimization, formal program specification and transformation, computational geometry, algorithmic game theory, computational biology, logic and type systems, and computability.
Deadlines and other dates:
Paper submission deadline:Monday August 16, 2010
Acceptance notification:Monday October 4, 2010
Final version of accepted papers due:Monday November 5, 2010
Early registration: Monday December 6, 2010
Conference dates: January 17-20, 2011
The proceedings of this event will be published by the Australian Computer Society (ACS) in the CRPIT Series (http://crpit.com/), and will also appear in the ACM digital library.
CATS 2011 is part of the Australasian Computer Science Week (ACSW), an international annual conference event, supported by the Computing Research and Education Association (CORE) in Australia. ACSW 2011 is hosted by Curtin University in Perth, Australia.
For more information please visit http://cats.it.usyd.edu.au/
Contact: taso viglas (aviglas+cats2011@gmail.com)
Tuesday, May 11, 2010
Back in the office
Today is my first day back at work after three months daddy leave. It's been great (I highly recommend it!) but it's also good to be back. I feel pretty energetic and motivated, but I'm sure it's just temporary.
As part of the new start I refurbished my homepage (can you guess what the banner depicts?), I bought two new sweaters and I just printed (I really should get an ereader) 6 papers that I have to review. Yes, I'm ready for work!
As part of the new start I refurbished my homepage (can you guess what the banner depicts?), I bought two new sweaters and I just printed (I really should get an ereader) 6 papers that I have to review. Yes, I'm ready for work!
Subscribe to:
Posts (Atom)
