SoCG 2008 Accepted Papers
The list of accepted papers for The 24th Annual ACM Symposium on Computational Geometry (SoCG) 2008 is out: (Hint, paper 40 looks good)
- Manor Mendel and Assaf Naor. Markov convexity and local rigidity of distorted metrics
- Noga Alon, Robert Berke, Maike Buchin, Kevin Buchin, Peter Csorba, Saswata Shannigrahi, Bettina Speckmann and Philipp Zumstein. Polychromatic Colorings of Plane Graphs
- Jinhee Chun, Matias Korman, Martin Nöllenburg and Takeshi Tokuyama. Consistent Digital Rays
- Eitan Yaffe and Dan Halperin. Approximating the Pathway Axis and the Persistence Diagram of a Collection of Balls in 3-Space
- Naoki Katoh and Shin-ichi Tanigawa. Fast Enumeration Algorithms for Non-crossing Geometric Graphs
- Ken Been, Martin N??llenburg, Sheung-Hung Poon and Alexander Wolff. Optimizing Active Ranges for Consistent Dynamic Map Labeling
- Hans Raj Tiwary and Khaled Elbassioni. On the Complexity of Checking Self-duality of Polytopes and its Relations to Vertex Enumeration and Graph Isomorphism
- Victor Chepoi, Feodor Dragan, Bertrand Estellon, Michel Habib and Yann Vaxes. Diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs
- Esther Arkin, Joseph Mitchell and Valentin Polishchuk. Maximum Thick Paths in Static and Dynamic Environments
- Julien Demouth, Olivier Devillers, Marc Glisse and Xavier Goaoc. Helly-type theorems for approximate covering
- Sarit Buzaglo, Ron Holzman and Rom Pinchasi. On $k$-intersecting curves and related problems
- Mohammad Ali Abam, Mark de Berg and Joachim Gudmundsson. A Simple and Efficient Kinetic Spanner
- Frederic Chazal and Steve Oudot. Towards Persistence-Based Reconstruction in Euclidean Spaces
- Ken Clarkson. Tighter Bounds for Random Projections of Manifolds
- Krzysztof Onak and Anastasios Sidiropoulos. Circular Partitions with Applications to Visualization and Embeddings
- Bernard Chazelle and Wolfgang Mulzer. Markov Incremental Constructions
- Kenneth L. Clarkson and C. Seshadhri. Self-Improving Algorithms for Delaunay Triangulations
- Frederic Cazals, Aditya Parameswaran and Sylvain Pion. Robust construction of the three-dimensional flow complex
- Herbert Edelsbrunner, John Harer and Amit Patel. Reeb Spaces of Piecewise Linear Mappings
- Evangelia Pyrga and Saurabh Ray. New Existence Proofs for $\epsilon$-Nets
- Lars Arge, Gerth Stølting Brodal and S. Srinivasa Rao. External memory planar point location with logarithmic updates
- Eric Berberich, Michael Kerber and Michael Sagraloff. Exact Geometric-Topological Analysis of Algebraic Surfaces
- Misha Belkin, Jian Sun and Yusu Wang. Discrete Laplace Operator on Meshed Surfaces
- Olivier Devillers, Marc Glisse and Sylvain Lazard. Predicates for 3D visibility
- Luca Castelli Aleardi, Eric Fusy and Thomas Lewiner. Schnyder woods for higher genus triangulated surfaces
- Erin Chambers, Jeff Erickson and Pratik Worah. Testing Contractibility in Planar Rips Complexes
- Rado Fulek, Andreas Holmsen and J??nos Pach. Intersecting convex sets by rays
- Noga Alon, Dan Halperin, Oren Nechushtan and Micha Sharir. The Complexity of the Outer Face in Arrangements of Random Segments
- Maarten L??ffler and Jack Snoeyink. Delaunay triangulations of imprecise points in linear time after preprocessing
- Erin Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus and Shripad Thite. Walking Your Dog in the Woods in Polynomial Time
- Jean-Daniel Boissonnat, Camille Wormser and Mariette Yvinec. Locally Uniform Anisotropic Meshing
- Adrian Dumitrescu, Micha Sharir and Csaba Toth. Extremal problems on triangle areas in two and three dimensions
- Timothy M. Chan. A (Slightly) Faster Algorithm for Klee's Measure Problem
- Timothy M. Chan. Dynamic Coresets
- Timothy M. Chan. On Levels in Arrangements of Curves, III: Further Improvements
- Minkyoung Cho and David Mount. Embedding and Similarity Search for Point Sets under Translation
- Jacob Fox and Janos Pach. Coloring K_k-free intersection graphs of geometric objects in the plane
- Timothy G. Abbott, Zachary Abel, David Charlton, Erik D. Demaine, Martin L. Demaine and Scott D. Kominers. Hinged Dissections Exist
- Vida Dujmovic, Ken-ichi Kawarabayashi, Bojan Mohar and David R. Wood. Improved upper bounds on the crossing number
- Pankaj Agarwal, Lars Arge, Thomas Mølhave and Bardia Sadri. I/O Efficient Algorithms for Computing Contour Lines on a Terrain
- Pankaj Agarwal, Bardia Sadri and Hai Yu. Untangling triangulations through local explorations
- Ileana Streinu and Louis Theran. Combinatorial Genericity and Minimal Rigidity
Election Day
I never made it to the consulate in Seattle in time to vote, unfortunately. I hope the right ones win. Anyways, DR decided to open their online live-tv to non-danish computers for today only, so I am currently sitting in my office at Duke watching the online coverage of the election, yay :)
We ordered some new machines the other day, four Dell XPS 720, two of those are in Denmark and the other two are currently in my office – look at these babies:
Flight Log
This blog needs more random junk! Being a flight geek I decided to keep track of my flight history, so far 46 legs in 18 months (!). I wil try to keep the log updated – mostly for my own amusement.
It would also be cool to attach pictures to the different places as well, similar to Mihai’s picture page.
[Update]: Forgot trip to Waterloo in December, haven’t bought the tickets yet but it will probably raise the grand total to 50 flights in 18 months.
[Update 2]: Yay, Air Canada has direct flights from RDU to Toronto (YYZ).
Danish Election
There’s an election in Denmark in November and I am kinda bummed that I won’t be there to vote. This document at the website for the Danish embassy in Washington says that I can go to a Danish consulate or embassy and vote by mail, the deadline for doing this is November 6. According to this list, the closest official danish mission is in Atlanta, Georgia or Charleston South Carolina, but that’s still quite a drive and I won’t have time to go there before November 6. On the other hand, there’s a Danish consulate in Seattle, and I am flying to seattle on November 6. It’s a long flight, but due to the time diffence I am going to be arriving in the late afternoon (about 3pm) and the Danish consulate closes at 4pm – which means that if I don’t get delayed in flight and get a very fast cab from the airport, I might just make it.
Israel
I have not been very good at updating this blog lately, I personally blame the fact that I have both Facebook and IM accounts. It is more convenient for me to update my facebook status, so my facebook-friends get more updates than the readers of this blog.
Anyways, a fortnight ago I travelled to Eilat, Israel for the European Symposium on Algorithms (ESA). The conference hotel was situated right by the red sea and a few hundred meters from the Jordan-border and sported several swimming pools and bars.
View from my hotel room’s balcony.
The lagoon on the back side of the hotel, the mountains in the distance are in Jordan. read more…
Noise Cancelling Headphones
I ended up buying a set of Sony MDR-NC60 at Circuit City here in Durham. So far I am very pleased with them, they come with airplane plugs and a handy bag and the sound quality is quite good. Furthemore, when the noise cancelling feature is turned on, the hum of A/C devices pretty much disappears, I am looking forward to see how effective they will be on airplanes. I constantly turn the volume up way to high on the crappy head phones that most airlines supply – hopefully I won’t have to do that with these.
Way to go Nokia
This is a very good Nokia campaign, it summarizes parts of what is soo wrong with the iPhone.
Here is Nokia’s product page for one of their devices, I like the focus of the ad campaign.
Car Update
Lars and Henrik arrived 7 days ago have been visiting Duke the past week. Lars went home yesterday and Henrik is staying a week more. Yesterday Henrik and I went to Jiffy-Lube in Durham and I had my car inspected (it passed!) and got an oil change. I am now pretty much done with all the talks related to the car, the only thing left is to send the old New Jersey plates back and to send my insurance company a copy of my registration.
I have a couple of lang-haul flights in the upcoming months (Seattle and Israel) and is currently seriously looking into noise canceling headphones. I tried a pair from Bose at an Apple Store in Raleigh two days ago and they were amazingly effective, they would make for a great companion on flight and on the train when I get back home. Unfortunately the technology is quite pricey with the top-of-the-range Bose headphones leading the field at around 300 dollars. I am also considering getting one of the new 8 gig iPod nanos (yes I know, I said I would never get one of those, leave me alone!) to go with the head phones. The iPod is actually considerably _cheaper_ than the headphones.
If anyone has any headphone recommendations, please put them in the comments to this post. I have read this positive New York Times review of different types of headphones, the technology looks pretty mature.
Talk Tomorrow
Tomorrow I am giving a talk at the Duke CS tri-seminar which is a seminar arranged by the duke algorithms grad students. If you happen to be in the area, feel free to stop by :).
Car Stuff
Today I went to two different North Caroline DMV office locations. I started out at one of the offices that grants drivers licenses. I had a short wait, a little interview followed by a written test and ending up with a actual driving test. Everything went fine and I left with a fine new North Carolina drivers license. Armed with that license, I went to the vehicle registration and title office where I successfully transferred the New Jersey title in the sellers name to a North Carolina title in my name. I left with a new registration and a new license plate (only one, NC does not require cars to have license plates in front).
*insert drum solo*
And here is a picture of the house I am staying in.
I am staying there with two other Duke cs grad students, I have a room on the first floor with windows facing away from the camera in this photo. I am very happy about my living arrangements, the room is big and we have a nice living room and a good kitchen.