Ernie's 3D Pancakes

Long week

New free computational geometry journal?

Joachim Gudmundsson and Pat Morin are discussing the possibility of establishing a new open access computational geometry journal, which would be completely free, for both readers and authors. So far, there are three relevant posts at Joachim's blog:

• The initial proposal: Editorial policies and responsibilities
• The first progress report: Software support and Creative Commons license
• The community poll: Should they do it?

At this moment, the poll results are almost unanimously in favor of the new journal, but with only ten votes, that's not saying much. Obviously the idea needs strong support from the computational geometry community before it can get off the ground. David Eppstein suggested raising this issue at the next SOCG business meeting (<steering-committee> Done! </steering-committee>), but certainly there are stakeholders who won't be at Aarhus. So speak up now!

I'm generally supportive, but I do have some concerns.

Is this just a screw-you replacement for Elsevier's ridiculously overpriced Computational Geometry: Theory & Applications (like similar efforts against Journal of Algorithms or Topology and Its Applications [pdf]), with the same topical coverage? Or is this journal intended to serve a broader need that the computational geometry existing journals do not? Will this be yet another journal for the SOCG+CCCG community, or will it also solicit high-quality results on metric embeddings, compressive sensing, manifold learning, computer-aided design, discrete differential geometry, nonholonomic motion planning, and other subfields at the intersection of geometry and algorithms that DCG, CGTA, IJCGA, SOCG, and CCCG traditionally discourage (or at least fail to attract)?

It's not enough to have potential readers ad writers clamoring for a free journal. The journal also needs a strong, committed, and outgoing editorial board. The success of Discrete & Computational Geometry is largely due to the tireless efforts of its founding editors, Eli Goodman and Ricky Pollack. Is there enough commitment from the community to make a new journal thrive? Joachim proposes a large and rotating editorial board, with 3-5 year terms, as a way to cut down on the workload. That's a fine idea, but then who chooses the editors? And who makes sure they continue to hunt down the best papers?

The lone and (of course) anonymous voice of dissent on Joachim's blog ("God. No. There is enough crap out there already.") has a point. The computational geometry community (traditionally defined) doesn't need yet another journal. Three computational geometry journals is already at least one too many. The only real way to make this fly, at least as a traditional computational geometry journal, would be to convince the editorial board of CGTA to resign en masse, like the boards of J. Alg and Top. Appl. did, and adopt the new home Joachim and Pat are building for them.

Hey, I'm all for that. Any journal that charges $31.50 for a single-page listing of its editorial board deserves to freeze in the coldest circle of hell. (You know, the one reserved for traitors to their benefactors—in this case, the authors and editors that do all the work—and people who talk in the theater.) But something tells me Jörg isn't going to be excited about abandoning his baby. I suggest starting with Kurt.

SOCG 2009 accepted papers

This is the list of papers accepted for presentation at the 25th Annual Symposium on Computational Geometry (SoCG'09), to be held at the University of Aarhus, Denmark, on June 8-10, 2009. (Sariel and Sorelle beat me to the punch, but there were a couple of last-minute changes.)

• Roel Apfelbaum and Micha Sharir
  An Improved Bound on the Number of Unit Area Triangles
• Boris Bukh, Jiri Matousek and Gabriel Nivasch
  Lower bounds for weak epsilon-nets and stair-convexity
• Joachim Giesen, Balint Miklos, Mark Pauly and Camille Wormser
  The Scale Axis Transform
• Francis Y. L. Chin, Zeyu Guo and He Sun
  Minimum Manhattan Network is NP-Complete
• Eyal Ackerman, Jacob Fox, János Pach and Andrew Suk
  On Grids in Topological Graphs
• Mohammad Abam and Mark de Berg
  Kinetic Spanners in R^d
• Naoki Katoh and Shin-ichi Tanigawa
  A Proof of the Molecular Conjecture
• Frédéric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas Guibas and Steve Oudot
  Proximity of Persistence Modules and their Diagrams
• Mark de Berg, Herman Haverkort and Constantinos Tsirogiannis
  Visibility Maps of Realistic Terrains have Linear Smoothed Complexity
• Gaiane Panina and Ileana Streinu
  Flattening single-vertex origami: the non-expansive case
• Oswin Aichholzer, Wolfgang Aigner, Franz Aurenhammer, Thomas Hackl, Bert Juettler, Margot Rabl and Elisabeth Pilgerstorfer
  Divide-and-Conquer for Voronoi Diagrams Revisited
• Marc Pouget, Sylvain Lazard, Elias Tsigaridas, Fabrice Rouillier, Luis Peñaranda and Jinsan Cheng
  On the topology of planar algebraic curves
• Sylvain Pion, Vicente H. F. Batista, David L. Millman and Johannes Singler
  Parallel Geometric Algorithms for Multi-Core Computers
• Pankaj Kumar Agarwal, Esther Ezra and Micha Sharir
  Near-Linear Approximation Algorithms for Geometric Hitting Sets
• Sandor Fekete, Dietmar Fey, Marcus Komann, Alexander Kroeller, Marc Reichenbach and Christiane Schmidt
  Distributed Vision with Smart Pixels
• Gunnar Carlsson, Vin de Silva and Dmitriy Morozov
  Zigzag Persistent Homology and Real-valued Functions
• Mikael Vejdemo-Johansson and Vin de Silva
  Persistent cohomology and circular coordinates
  
• Andrea Vattani
  k-means requires exponentially many iterations even in the plane
• Natasa Jovanovic, Jan Korst, Ramon Clout, Verus Pronk and Ludo Tolhuizen
  Candle in the Woods: Asymptotic Bounds on Minimum Blocking Sets
• Bernard Chazelle and Wolfgang Mulzer
  Computing Hereditary Convex Structures
• Nabil Mustafa and Saurabh Ray
  PTAS for geometric hitting set problems via Local Search
• Jean-Daniel Boissonnat, Olivier Devillers and Samuel Hornus
  An efficient implementation of the Delaunay triangulation and its graph in medium dimension
• Sang Won Bae and Kyung-Yong Chwa
  The Geodesic Farthest-Site Voronoi Diagram in a Polygonal Domain with Holes
• Chuanjiang Luo, Jian Sun and Yusu Wang
  Integral Estimation from Point Cloud in R^d: a Geometric View
• David Eppstein, Elena Mumford, Bettina Speckmann and Kevin Verbeek
  Area-Universal Rectangular Layouts
• Andrea Francke and Michael Hoffmann
  Maximum Degree Four Euclidean Minimum Spanning Tree is NP-hard
• Rom Pinchasi
  Halving Lines and Measure Concentration in the Plane
• Tamal Dey and Kuiyu Li
  Cut Locus and Topology from Surface Point Data
• Marc van Kreveld and Rodrigo Silveira
  Embedding Rivers in Polyhedral Terrains
• Mashhood Ishaque, Bettina Speckmann and Csaba Toth
  Shooting permanent rays among disjoint polygons in the plane
• Chandra Chekuri, Ken Clarkson and Sariel Har-Peled
  On the Multi-Cover Problem in Geometric Settings
• Timothy Chan and Sariel Har-Peled
  Approximation Algorithms for Maximum Independent Set of Pseudo-Disks
• Bernd Gärtner and Martin Jaggi
  Core-Sets for Polytope Distance
• Kasturi Varadarajan
  Epsilon Nets and Union Complexity
• Timothy M. Chan and Eric Y. Chen
  Optimal In-Place Algorithms for 3-d Convex Hulls and 2-d Segment Intersection
• Luc Habert and Michel Pocchiola
  Arrangements of double pseudolines
• Friedrich Eisenbrand, Nicolai Haehnle and Thomas Rothvoss
  Diameter of Polyhedra: Limits of Abstraction
• Chee Yap and Long Lin
  Parametrizability and Nonlocal Isotopy: An Approach to Efficient Approximation of Nonsingular Curves
• Erin Chambers, Jeff Erickson and Amir Nayyeri
  Minimum Cuts and Shortest Homologous Cycles
• Don Sheehy and Gary Miller
  Approximate Center Points with Proofs
• Csaba Toth
  Binary Plane Partitions for Disjoint Line Segments
• Peyman Afshani, Chris Hamilton and Norbert Zeh
  Cache-Oblivious Range Reporting With Optimal Queries Requires Superlinear Space
• Glencora Borradaile, James Lee and Anastasios Sidiropoulos
  Randomly removing g handles at once
• Peyman Afshani, Chris Hamilton and Norbert Zeh
  A Unified Approach for Cache-Oblivious Range Reporting and Approximate Range Counting

Dentist + Kittens = WIN!

Watch them in order:

• David after the Dentist!
• Kittens inspired by Kittens!!
• Kittens after the dentist!!!