Ernie's 3D Pancakes

Toronto is hiring in computational geometry

Toronto's Computer Science Department is searching for new tenure-track faculty in computational geometry. Apply by November 15!

The Faculty of Arts and Science at the University of Toronto invites applications for up to three tenure-stream appointments in the Department of Computer Science in the areas of Knowledge Representation and Reasoning, Computer Systems, and Computational Geometry. The appointment(s) will be at the rank of Assistant Professor and will commence July 1, 2019.

Candidates in all areas of Computer Science that touch upon knowledge representation and reasoning, computer systems, and computational geometry in the broadest possible sense will be considered. We are especially interested in exceptional candidates who transcend traditional computing research topics and complement our existing strengths....

Application material for the position should be submitted online through AcademicJobsOnline at https://academicjobsonline.org/ajo/jobs/11954. It should include the candidate’s curriculum vitae, a list of publications, a research statement, a teaching statement, and at least three letters of reference (on letterhead, signed and scanned) uploaded to AcademicJobsOnline directly by the writers. Review of applications will begin on November 15, 2018 and applicants should endeavor to have all materials submitted by then, however applications will be accepted until the position is filled.

Three talks at SOCG

I just came back from a lovely trip to Rio de Janeiro for SOCG. This year's meeting was quite a bit busier than usual, with three different presentations lasting in total almost three hours. In order of increasing importance:

• On Monday morning, I presented my paper "Efficiently hex-meshing things with topology" (slides). The paper answers the following question: When can a polyhedron with quadrilateral faces be partitioned into a complex of topological cubes, without refining the boundary? It is not hard to see that the number of quads must be even. For even surface meshes, I prove that the following equivalent conditions are necessary and sufficient:
  • No odd cycle in the surface graph is the boundary an immersed surface in the interior.
  • The dual of the surface graph is the boundary of an immersed surface in the interior.
  The paper says "null-homologous" instead of "the boundary of an immersed surface", but these two phrases are synonymous. This generalizes earlier results by Thurston and Mitchell for polyhedra with genus zero, where an even number of quads is sufficient, and by Eppstein for bipartite surface meshes, which always have an even number of facets. The proof is constructive.

• On Monday afternoon, in a fantastic workshop on mesh generation organized by Marcelo Siqueira, I gave a one-hour survey talk on theoretical hexahedral meshing (slides). The first chunk of the talk establishes some basic definitions, which are usually left unstated by both computational geometers and mesh generators. In particular, in actual hexahedral finite-element meshes, the word "hexahedron" does not mean a convex polyhedron with six planar facets, but the multilinear hull of eight labeled points; the facets of a "hex element" are ruled surface patches. There are lots of good practical heuristics for building hex meshes, but no fully automatic methods, or as I usually call them, algorithms. If we allow boundary refinement, hex meshing is actually easy — just triangulate and then refine each tet into four hexes — but only if we don't care about mesh quality. If we don't allow boundary refinement, even the existence of hex meshes is a more subtle open problem, leading to lots of interesting geometry and topology, but again, even where we have algorithms, we have nothing with useful quality guarantees. The big open problem is to define a general class of input domains, define a useful quality measure, and then describe an algorithm that provably generates a high-quality mesh for any domain in the class, as Bern, Eppstein, Ruppert, Shewchuk, and many others have done for triangular and tetrahedral meshing.

• Finally, on Tuesday evening, I ran my first SOCG business meeting as steering commitee chair. David Eppstein's official minutes and the complete meeting slides (mirror) are now available on www.computational-geometry.org, but here are some highlights:
  • There were 150 attendees, which is less than Paris in 2011 and Chapel Hill in 2012, but more than the six years before that. Thanks to incredibly low student registration fees, there were 66 registered students.

  • The Best Paper award went to Victor Alvarez and Raimund Seidel, for their excellent paper "A simple aggregative algorithm for counting triangulations of planar point sets and related problems".

  • The video and multimedia committee raised the awesomeness standard for submissions. They also distributed this year's videos much more widely, not only on the SOCG web page and in the Digital Library, but also on YouTube and at imaginary.org.

  • The SOCG 2014 PC chairs are Siu-Wing Cheng and Olivier Devillers.

  • Starting with Victor and Raimund this year, SOCG Best Paper Award winners will be invited to submit a full version of their paper to Journal of the ACM.

  • Starting next year, we expect to offer NSF travel support to SOCG for US students and postdocs.

  • There was strong support for the idea of co-locating SOCG with STOC in 2016, moderated by lots of pertinent logistical questions. I said "I don't know yet; we'll have to work that out" a lot.

  • SOCG 2015 will be held at TU Eindhoven, in the Netherlands. The other bidders, which all tied for second place in the first voting round, were Braunschweig, Germany; Brisbane, Australia; and Portland, Oregon.

  • There will be a third and final vote regarding the future relationship between SOCG and ACM, which will take place in October. I've set up a discussion blog, where I will describe issues related to the vote. I will also invite posts from other members of the SOCG community, ACM representatives, and organizers of other conferences. My goal is to ensure that all relevant stakeholders have a voice before voting begins.

  Whew!

  One important item was not announced at the business meeting. The Best Student Presentation award was shared by two students:

  • João Peixão, for his presentation of "Parameterized Complexity of Discrete Morse Theory"
  • Luis Barba, for his presentation of "Bichromatic Compatible Matchings"

  These two winners were announced Thursday morning, after all student speakers had presented their papers. The award is based on audience evaluations.

SOCG(T) 2012

The list of accepted papers for SOCG 2012 has been released. By my admittedly liberal count, 21 of the 44 accepted papers qualify as computational topology. Maybe it's time to add "...and Topology" to the name of the conference!

(Ha, ha, only serious.)

• Michal Adamaszek and Juraj Stacho.
  Algorithmic complexity of finding cross-cycles in flag complexes
• Muhammad Jawaherul Alam, Therese Biedl, Stefan Felsner, Michael Kaufmann, Stephen Kobourov and Torsten Ueckerdt.
  Computing Cartograms with Optimal Complexity
• Therese Biedl and Martin Vatshelle.
  The point-set embeddability problem for plane graphs
• Jean-Daniel Boissonnat, Ramsay Dyer and Arijit Ghosh.
  Stability of Delaunay-type structures for manifolds
• Ciprian Borcea, Ileana Streinu, and Shin-Ichi Tanigawa.
  Periodic body-and-bar frameworks
• Guillermo D. Canas and Steven Gortler.
  Duals of Orphan-Free Anisotropic Voronoi Diagrams are Triangulations
• Siu-Wing Cheng, Jiongxin Jin, and Man-Kit Lau.
  A Fast and Simple Surface Reconstruction Algorithm
• Éric Colin De Verdière, Grégory Ginot, and Xavier Goaoc.
  Multinerves and Helly numbers of acyclic families
• Éric Colin De Verdière and Arnaud De Mesmay.
  Testing graph isotopy on surfaces
• Herbert Edelsbrunner, Brittany Terese Fasy, and Günter Rote.
  Add Isotropic Gaussian Kernels at Own Risk: More and More Resiliant Modes in Higher Dimensions
• Herbert Edelsbrunner and Michael Kerber.
  Alexander Duality for Functions: the Persistent Behavior of Land and Water and Shore
• Jeff Erickson and Amir Nayyeri.
  Tracing Compressed Curves in Triangulated Surfaces
• Silvia Fernandez, Bernardo M. Abrego, Oswin Aichholzer, Pedro Ramos, and Gelasio Salazar.
  The 2-page crossing number of $K_{n}$
• Anna Gundert and Uli Wagner.
  On Laplacians of Random Complexes
• Sariel Har-Peled, Amir Nayyeri, Mohammad Salavatipour, and Anastasios Sidiropoulos.
  How to Walk Your Dog in the Mountains with No Magic Leash
• Salman Parsa.
  A Deterministic O(m log m) Time Algorithm for the Reeb Graph
• Jens M. Schmidt and Pavel Valtr.
  Cubic Plane Graphs on a Given Point Set.
• Micha Sharir, Adam Sheffer, and Emo Welzl.
  Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique
• Don Sheehy.
  Linear-Size Approximations to the Vietoris-Rips Filtration
• Andrew Suk.
  Disjoint edges in complete topological graphs
• Amit Chattopadhyay, Gert Vegter, and Chee Yap.
  Certified Computation of planar Morse-Smale Complexes of Smooth Functions

SOCG 2012 call for papers, videos, and multimedia

At Tamal Dey's request, here is the

CALL FOR PAPERS, VIDEOS, and MULTIMEDIA

28th Annual Symposium on Computational Geometry (SoCG 2012)

June 17-20, 2012 (tentative)
University of North Carolina, Chapel Hill
In cooperation with ACM SIGACT and SIGGRAPH
Web-page: http://socg2012.web.unc.edu

The Twenty-Eighth Annual Symposium on Computational Geometry will be held in University of North Carolina, Chapel Hill. We invite submissions of high-quality papers that describe original research on issues related to computational problems arising from geometric considerations. We also invite submissions of original videos and multimedia on these same themes. This year, SoCG will be collocated with a workshop, Computational Geometry: Applications, Practice, and Theory (CG:APT), whose call for submissions (due Feb 27) will be distributed separately.

The topics of the SoCG 2012 Symposium reflect the rich diversity of research interests in computational geometry. They are intended to highlight both the depth and scope of computational geometry, and to invite fruitful interactions with other disciplines. Topics of interest include, but are not limited to:

• design, analysis, and implementation of geometric algorithms and data structures; lower bounds on the computational complexity of geometric problems;
• mathematical, numerical, algebraic, and experimental issues arising in geometric algorithms and heuristics; discrete and combinatorial geometry; computational topology;
• novel applications of computational geometry in computer graphics, geometric modeling, computer-aided design and manufacturing, scientific computing, geographic information systems, database systems, robotics, computational biology, machine learning, sensor networks, biomedical imaging, combinatorial optimization, statistical analysis, discrete differential geometry, theoretical computer science, graph drawing, pure mathematics, and other fields; novel problems in computational geometry arising from these fields.

Important Dates

• November 22, 2011: Paper titles and abstracts (at most 300 words) due (23:59, Honolulu time)
• December 2, 2011: Paper submissions due (23:59, Honolulu time)
• February 17, 2012: Notification of acceptance/rejection of papers
• February 27, 2012 : Submissions of videos and multimedia due (23:59, Honolulu Time)
• March 8, 2012: Notification of acceptance/rejection of video/multimedia
• March 22, 2012: Camera-ready versions due for papers and video/multimedia abstracts
• April 26, 2012: Final versions of video/multimedia due
• June 17-20, 2012 (tentative): Symposium in Chapel Hill, North Carolina

Call for Papers

We invite submissions of high-quality papers describing original research on geometric algorithms and data structures, their mathematical foundations and correctness, their implementation, and their applications.

Final versions of accepted papers will be published by ACM in the symposium proceedings. Proceedings will be distributed to symposium participants and will also be available from ACM for purchase and through the ACM digital library. An author of each accepted paper will be expected to attend the Symposium and give a presentation (approximately 20 minutes) of the paper. Authors of a selection of papers from the conference will be invited to submit extended versions of their papers to a special issue of one or more journals. This year we also plan to confer two Best Paper Awards, and a Best Student Presentation Award. The Student Presentation award will be based on the quality of the presentation of a paper by a student during the conference.

Paper Submission

All submissions should be made electronically; see the EasyChair SoCG2012 web page https://www.easychair.org/conferences/?conf=socg2012 for detailed submission instructions (to be available shortly). If electronic submission is not feasible, please contact the program committee chairs, Tamal Dey and Sue Whitesides, well in advance of the submission deadlines.

Submission Guidelines

Papers should be submitted in the form of an extended abstract, which begins with the title and abstract page that contains the title of the paper, each author's name, affiliation, and e-mail address followed by a short abstract. The main body of the extended abstract should begin with a precise statement of the problem considered, a succinct summary of the results obtained (emphasizing the significance, novelty, and potential impact of the research), and a clear comparison with related work. The remainder of the extended abstract should provide sufficient detail to allow the program committee to evaluate the validity, quality, and relevance of the contribution. Clarity of presentation is very important; the whole extended abstract should be written carefully, taking into consideration that it will be read and evaluated by both experts and non-experts, often under tight time constraints.

Submissions should be typeset in single column format, using 11-point or larger font, with at least 1 inch/2.54 cm margins and single line spacing. Excluding the title page and bibliography, the extended abstract must not exceed 10 pages. Submissions deviating from these guidelines risk rejection without consideration of their merits.

All necessary details to verify the results must be provided. If they cannot fit within the 10-page limit, a clearly marked appendix containing omitted details should be included. Appendices are not counted in the 10 page limit, so while they may serve as a reference, they will be read by the program committee members at their discretion. The paper excluding the appendix should clearly describe the results and the approach to achieve them, and give sufficient confidence for their validity. The appendix should then give all the necessary details to verify correctness.

Anticipating the usual high overall quality of submissions, the program committee intends to interpret the scope of the conference broadly, and will seriously consider all papers that are of significant interest to our research community.

Authors must submit the title and an abstract (at most 300 words) of their papers by November 22, 2011. This pre-submission will be used to help make program committee reading assignments. Extended abstracts must be received by December 2, 2011 (23:59, Honolulu time). There will be no extension of these deadlines; late submissions will not be considered. Authors will be notified of acceptance or rejection by February 17, 2012. The final proceedings papers must be formatted in accordance with ACM proceedings guidelines; LaTeX style files will be made available to authors of accepted papers.

Concurrent submission of the same (or essentially the same) abstract to SoCG and to another conference with published proceedings is not allowed. An extended abstract of a paper that is under journal review, or scheduled for publication in a journal after June 2012, may be submitted, when it is clear that the extended abstract differs substantially from the journal version. In such cases, the authors must include the journal version in an appendix that clearly identifies the status of the journal submission.

Program Committee

• Pankaj Agarwal (Duke University)
• Dominique Attali (Gipsa-Lab, Grenoble)
• Gill Barequet (Technion-Israel Institute of Technology)
• Mark de Berg (Technische Universiteit, Eindhoven)
• Danny Chen (University of Notre Dame)
• Tamal Dey (The Ohio State University) (co-chair)
• Vida Dujmović (Carleton University)
• David Eppstein (University of California, Irvine)
• Leonidas Guibas (Stanford University)
• Sylvain Lazard (INRIA, Nancy Grand Est)
• Dinesh Manocha (The University of North Carolina at Chapel Hill)
• Steve Oudot (INRIA Saclay)
• Konrad Polthier (Freie Universität Berlin)
• Edgar Ramos (Universidad Nacional de Colombia, Medellín)
• Jian Sun (Tsinghua University)
• Takeshi Tokuyama (Tohoku University)
• Yusu Wang (The Ohio State University)
• Max Wardetzky (University of Göttingen)
• Sue Whitesides (University of Victoria, British Columbia) (co-chair)

---

Call for Video and Multimedia Presentations

Video and multimedia presentations are sought for the 21st Annual Video and Multimedia Review of Computational Geometry, to accompany the 28th Annual Symposium on Computational Geometry. This review showcases the use of visualization in computational geometry for exposition and education, for visual exploration of geometry in research, and as an interface and a debugging tool in software development. Algorithm animations, visual explanations of structural theorems, descriptions of applications of computational geometry, and demonstrations of software systems are all appropriate.

Three to five minutes is ideal for most presentations; eight minutes is the upper limit. Accepted video and multimedia presentations will have an abstract in the published conference proceedings; video/multimedia authors will have an opportunity to present their work at the Symposium during a dedicated video session. Accepted presentations will be available online in various formats in a web proceedings. See http://www.computational-geometry.org/ for examples of previous years' proceedings.

Submissions of video clips in QuickTime or MPEG-4 compressed formats (e.g., XviD or DivX version 6) are encouraged. We also encourage submissions of Macromedia Flash, Java applets, and limited forms of other multimedia or software. These formats must come with a script that will allow them to be distributed in both interactive and canned Quicktime or MPEG video formats. In case of doubt, please email the Video and Multimedia Program chair.

Each submission should include a one or two-page description of the material shown in the presentation, and where applicable, the techniques used in the implementation. The final two-page descriptions must be formatted according to the guidelines for proceedings. LaTeX style files will be provided to authors of accepted presentations.

Submission

Submissions should be deposited online where they are accessible through the web or via FTP. Send email to the Video/Multimedia committee chair, Christian Knauer by 23:59 Honolulu Time, Monday, February 27, 2012, with the following information: the names and institutions of the authors, the email address of the corresponding author, and instructions for downloading the submission. For ease of sharing and viewing, we encourage (but do not require) that each submission be uploaded to YouTube, and that the corresponding URL be included with the submission.

We explicitly encourage video/multimedia submissions that support papers submitted to the Symposium. Submitted papers and associated video/multimedia submissions will be treated entirely separately by the respective committees: acceptance or rejection of one will not influence acceptance or rejection of the other.

Authors will be notified of acceptance or rejection, and given reviewers' comments by March 8, 2012. For each accepted submission, the final version of the 2-page textual description will be due by March 22, 2012 (electronically) for inclusion in the proceedings. Final versions of accepted video/multimedia presentations will be due April 26, 2012 in the best format available.

Important Dates

• Feb. 27, 2012: Video and Multimedia submissions due
• Mar. 8, 2012: Notification for Video/MM submissions (23:59 Honolulu time)
• Mar. 22, 2012: Camera-ready video/MM abstracts due
• Apr. 26, 2012: Final versions of video/MM presentations due

Video and Multimedia Presentation Program Committee

• Helmut Alt -Freie Universität Berlin
• Sandor Fekete - TU Braunschweig
• Panos Giannopoulos - Universität Bayreuth
• Xavier Goaoc - INRIA Nancy Grand Est
• Rolf Klein - Universität Bonn
• Christian Knauer (chair) - Universität Bayreuth
• Joseph S. B. Mitchell - SUNY Stony Brook
• Bettina Speckmann - TU Eindhoven
• Fabian Stehn - Universität Bayreuth
• Alexander Wolff - Universität Würzburg

---

SOCG 2012 Local Arrangements

Jack Snoeyink, Chair

SOCG Steering Committee (2009-2012)

• Jack Snoeyink, chair (University of North Carolina)
• Mark de Berg, secretary (TU Eindhoven)
• Joe Mitchell (SUNY Stony Brook)
• Guenter Rote (FU Berlin)
• Monique Teillaud (INRIA Sophia Antipolis - Méditerranée)

Geometry and topology at SODA 2012

Here's a selection of computational geometry and topology papers accepted to SODA 2012. As usual, this list is neither exclusive nor exhaustive; for many papers, I'm just guessing about the content from the title and/or authors.

Geometry

Yes, most data structure papers count.

• The maximum number of faces of the Minkowski sum of two convex polytopes
  Menelaos I. Karavelas and Eleni Tzanaki
• Physarum Can Compute Shortest Paths
  Vincenzo Bonifaci, Kurt Mehlhorn, and Girish Varma
• A Near-Linear Algorithm for Projective Clustering Integer Points
  Kasturi Varadarajan and Xin Xiao
• On a Linear Program for Minimum-Weight Triangulation
  Arman Yousefi and Neal Young
• Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts
  Anne Driemel and Sariel Har-Peled
• I/O-Efficient Data Structures for Colored Range and Prefix Reporting
  Kasper Green Larsen and Rasmus Pagh
• Sparser Johnson-Lindenstrauss Transforms
  Daniel Kane and Jelani Nelson
• Information Dissemination via Random Walks in d-Dimensional Space
  Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun, and Yajun Wang
• Fast zeta transforms for point lattices
  Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, and Pekka Parviainen
• Partial match queries in random quadtrees
  Nicolas Broutin, Ralph Neininger, and Henning Sulzbach
• Packing anchored rectangles
  Adrian Dumitrescu and Csaba Toth
• Confluent Persistence Revisited
  Sebastien Collette, John Iacono, and Stefan Langerman
• Using Hashing to Solve the Dictionary Problem (In External Memory)
  John Iacono and Mihai Patrașcu
• Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
  Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir
• Computing distance between piecewise linear bivariate functions
  Boris Aronov and Guillaume Moroz
• Algorithms and Data Structures for the Transportation Problem in Geometric Settings
  R Sharathkumar and Pankaj Agarwal
• Fully Persistent B-trees
  Gerth Stølting Brodal, Spyros Sioutas, Konstantinos Tsakalidis, and Kostas Tsichlas
• Dimension reduction for finite trees in l_1
  James Lee, Arnaud De Mesmay, and Mohammad Moharrami
• Bidimensionality and Geometric Graphs
  Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh

Topology

Yes, most planar graph papers count.

• Computing all maps into a sphere
  Martin Cǎdek, Marek Krčál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, and Uli Wagner
• Exact Distance Oracles for Planar Graphs
  Shay Mozes and Christian Sommer
• Spanning closed walks and TSP in 3-connected planar graphs
  Ken-Ichi Kawarabayashi and Kenta Ozeki
• Approximate Tree Decompositions of Planar Graphs in Linear Time
  Frank Kammer and Torsten Tholey
• Finding an induced path of given parity in planar graphs in polynomial time
  Marcin Kaminski and Naomi Nishimura
• Near optimal distance oracle for planar digraphs avoiding a failed node or link
  Utkarsh Lath, Surender Baswana, and Anuradha Mehta
• Global Minimum Cuts in Surface Embedded Graphs
  Jeff Erickson, Kyle Fox, and Amir Nayyeri
• The Maximum Degree of Random Planar Graphs
  Michael Drmota, Omer Gimenez, Marc Noy, Konstantinos Panagiotou, and Angelika Steger
• Local Homology Transfer and Stratification Learning
  Paul Bendich, Bei Wang, and Sayan Mukherjee

Geometry and data structures at WADS 2011

The list of papers accepted to WADS 2011 is out. Here are the papers I could identify from the titles as either computational geometry or data structures. As usual, I can't guarantee that these lists are either exclusive or exhaustive; if a paper qualified for both lists, I just picked one. Sorry if I missed your paper.

Congratulations to all the authors, but especially to my PhD student Kyle Fox on his first solo paper, his second student-only paper, and his second paper!

Computational Geometry

• Mohammad Ali Abam, Mark De Berg, and Amirali Khosravi.
  Piecewise-Linear Approximations of Uncertain Functions

• Patrizio Angelini, Till Bruckdorfer, Marco Chiesa, Fabrizio Frati, Michael Kaufmann, and Claudio Squarcella.
  On the Area Requirements of Euclidean Minimum Spanning Trees

• Spyros Angelopoulos, Alejandro Lopez-Ortiz, and Konstantinos Panagiotou.
  Multi-target Ray Searching Problems

• Esther M. Arkin, Claudia Dieckmann, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Lena Schlipf, and Shang Yang.
  Convex Transversals

• Boris Aronov and Muriel Dulieu.
  How to Cover a Point Set with a V-Shape of Minimum Width

• Boris Aronov, Muriel Dulieu, and Ferran Hurtado.
  Witness Rectangle Graphs

• Mark de Berg, Amirali Khosravi, Sander Verdonschot, and Vincent Van Der Weele.
  On Rectilinear Partitions with Minimum Stabbing Number

• Therese Biedl, Stephane Durocher, Celine Engelbeen, Samuel Fiorini, and Maxwell Young.
  Faster Optimal Algorithms For Segment Minimization With Small Maximal Value

• Therese Biedl and Lesvia Elena Ruiz Velázquez.
  Orthogonal cartograms with few corners per face

• Markus Bläser, Bodo Manthey, and B. V. Raghavendra Rao.
  Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals

• Prosenjit Bose, Paz Carmi, Mirela Damian, Robin Flatland, Matthew Katz, and Anil Maheshwari.
  Switching to Directional Antennas with Constant Increase in Radius and Hop Distance

• Kevin Buchin, David Eppstein, Maarten Löffler, Martin Nöllenburg, and Rodrigo Silveira.
  Adjacency-Preserving Spatial Treemaps

• Erin Chambers, Sandor Fekete, Hella-Franziska Hoffmann, Dimitri Marinakis, Joseph Mitchell, Venkatesh Srinivasan, Ulrike Stege, and Sue Whitesides.
  Connecting a Set of Circles with Minimum Sum of Radii

• Timothy M. Chan and Vinayak Pathak.
  Streaming and Dynamic Algorithms for Minimum Enclosing Balls in High Dimensions

• Danny Z. Chen and Haitao Wang.
  New Algorithms for 1-D Facility Location and Path Equipartition Problems

• Tobias Christ.
  Beyond Triangulation: Covering Polygons with Triangles

• Atlas F. Cook IV, Anne Driemel, Sariel Har-Peled, Jessica Sherette, and Carola Wenk.
  Computing the Fréchet Distance Between Folded Polygons

• Anne Driemel, Herman Haverkort, Maarten Löffler, and Rodrigo Silveira.
  Flow Computations on Imprecise Terrains

• David Eppstein, Michael Goodrich, and Maarten Löffler.
  Tracking Moving Objects with Few Handovers

• P. Thomas Fletcher, John Moeller, Jeff Phillips, and Suresh Venkatasubramanian.
  Horoball Hulls and Extents in Positive Definite Space

• Jie Gao and Dengpan Zhou.
  Resilient and Low Stretch Routing Through Embedding into Tree Metrics

• Andreas Gemsa, Martin Nöllenburg and Ignaz Rutter.
  Consistent Labeling of Rotating Maps

• Michael Hoffmann, Micha Sharir, Adam Sheffer, Csaba Toth, and Emo Welzl.
  Counting Plane Graphs: Flippability and its Applications

• Allan Jorgensen, Maarten Löffler, and Jeff Phillips.
  Geometric Computations on Indecisive Points

• Pegah Kamousi, Timothy Chan, and Subhash Suri.
  Closest Pair and the Post Office Problem for Stochastic Points

• Yakov Nekrich.
  A Fast Algorithm for Three-Dimensional Layers of Maxima Problem

• Valentin Polishchuk and Mikko Sysikaski.
  Faster algorithms for minimum-link paths with restricted orientations

• Shay Solomon.
  The MST of Symmetric Disk Graphs (in Arbitrary Metrics) is Light

Data Structures

• Paul Christiano, Erik D. Demaine, and Shaunak Kishore.
  Lossless Fault-Tolerant Data Structures with Additive Overhead

• Pooya Davoodi, Gerth Stølting Brodal, and Srinivasa Rao Satti.
  Path Minima Queries in Dynamic Weighted Trees

• Johannes Fischer.
  Inducing the LCP-Array

• Kyle Fox.
  Upper Bounds for Maximally Greedy Binary Search Trees

• Michael Fredman.
  On the matter of dynamic optimality in an extended model for tree access operations

• Jing He, Hongyu Liang, and Guang Yang.
  Reversing Longest Previous Factor Tables is Hard

• Meng He and Ian Munro.
  Space Efficient Data Structures for Dynamic Orthogonal Range Counting

• Brent Heeringa, Marius Cătălin Iordan, and Louis Theran.
  Searching in Dynamic Tree-Like Partial Orders

• Shoshana Neuburger and Dina Sokol.
  Succinct 2D Dictionary Matching With No Slowdown

• Yahav Nussbaum.
  Improved Distance Queries in Planar Graphs

Computational topology at SOCG and EuroCG 2011

As expected, the number of papers accepted to SOCG 2011 is significantly larger than in past years — 55 instead of the traditional 42–45. Perhaps as a result, the acceptance list includes an unusually large number of computational topology papers. Here is a (likely incomplete) list:

• Dominique Attali, Andre Lieutier, and David Salinas. Efficient data structure for representing and simplifying simplicial complexes in high dimension
• Dominique Attali, Andre Lieutier, and David Salinas. Vietoris-Rips complexes also provide topologically correct reconstructions of sampled shapes
• Benjamin A. Burton and Melih Ozlen. A tree traversal algorithm for decision problems in knot theory and 3-manifold topology
• Benjamin A. Burton. The Pachner graph and the simplification of 3-sphere triangulations
• Manuel Caroli and Monique Teillaud. Delaunay Triangulations of Point Sets in Closed Euclidean d-Manifolds
• Chao Chen and Michael Kerber. An Output-Sensitive Algorithm for Persistent Homology
• Frédéric Chazal, Leonidas Guibas, Steve Oudot and Primoz Skraba. Persistence-Based Clustering in Riemannian Manifolds
• Tamal Dey and Yusu Wang. Reeb Graphs: Approximation and Persistence
• Nathan Dunfield and Anil Hirani. The Least Spanning Area of a Knot and the Optimal Bounding Chain Problem
• Jeff Erickson. Shortest nontrivial cycles in directed surface graphs
• Sariel Har-Peled and Benjamin Raichel. The Frechet Distance Revisited and Extended
• Nikola Milosavljevic, Dmitriy Morozov, and Primož Škraba. Zigzag Persistent Homology in Matrix Multiplication Time

And here is a similar list for EuroCG:

• Amit Chattopadhyay and Gert Vegter. Certified Computation of Morse-Smale Complexes on Implicit Surfaces
• Chao Chen and Michael Kerber. Persistent Homology Computation with a Twist
• Shervin Daneshpajouh, Mohammad Ali Abam, Lasse Deleuran and Mohammad Ghodsi. Computing Strongly Homotopic Line Simplification in the Plane
• Marc Pouget, Sylvain Lazard, Fabrice Rouillier and Yacine Bouzidi. New bivariate system solver and topology of algebraic curves
• Christian Scheffer and Jan Vahrenhold. Learning a 2-Manifold with a Boundary in R^3

Also, you can occasionally find me here.

Geometry and topology at SODA 2011

Andrew McGregor posts a link to the list of accepted papers at SODA 2011. The list bizarrely only includes the contact authors for each paper, rather than the complete list of authors, perhaps because HotCRP (the submission system) did not actually ask for a complete list of authors for each submission.

Anyway, here is a non-exclusive, non-exhaustive list of computational geometry and topology papers that were accepted, with complete author lists when I could reconstruct them. Starred* authors are students (as far as I can tell).

Algorithms and Hardness for Subspace Approximation

Amit Deshpande, Kasturi Varadarajan, Madhur Tulsiani, Nisheeth K. Vishnoi

An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform

Nir Ailon and Edo Liberty

An Optimal-Time Construction of Sparse Euclidean Spanners with Tiny Diameter

Shay Solomon*

Approximate Nearest Neighbor Search for Low Dimensional Queries

Sariel Har-Peled and Nirman Kumar*

Collapse

Uri Zwick and Günter Rote

Computing Replacement Paths in Surface Embedded Graphs

Jeff Erickson and Amir Nayyeri*

Computing Shortest Paths amid Pseudodisks

Danny Z. Chen and Haitao Wang

Convex hulls of hyperspheres and convex hulls of convex polytopes lying on parallel hyperplanes

Menelaos I. Karavelas, Eleni Tzanaki

Dimensionality Reduction: Beyond the Johnson-Lindenstrauss Bound

Yair Bartal, Benjamin Recht, and Leonard J. Schulman

Embedding Stacked Polytopes on a Polynomial Sized Grid

André Schulz (inter alia?)

Fast, precise and dynamic distance queries

Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, and Liam Roditty

I/O-Efficient contour queries on terrains

Pankaj K. Agarwal, Thomas Mølhave, and Bardia Sadri

Improved Bound for the Union of Fat Triangles

Esther Ezra and Micha Sharir

Minimum Cuts and Shortest Non-Separating Cycles via Homology Covers

Jeff Erickson and Amir Nayyeri*

Mobile Geometric Graphs: Detection, Coverage and Percolation

Yuval Peres, Alistair Sinclair, Perla Sousi, and Alexandre Stauffer

New Approximation Algorithms for Minimum Enclosing Convex Shapes

Ankan Saha, S.V.N. Vishwanathan, and Xinhua Zhang

Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Low Error

T.S. Jayram and David Woodruff

Overlap properties of geometric expanders

Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, and Janos Pach

Shortest Non-Crossing Walks in the Plane

Jeff Erickson and Amir Nayyeri*

Streaming k-means on Well-Clusterable Data

Adam Meyerson, Alan Roytman, Michael Shindler, and Brian Tagiku

Succinct Convex Greedy Drawing of 3-Connected Plane Graphs

Huaming Zhang and Xin He

The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus

Shayan Oveis Gharan* and Amin Saberi

Triangulating the Square: Quadtrees and Delaunay Triangulations are Equivalent

Maarten Löffler and Wolfgang Mulzer*

SOCG 2010 Call for Submissions

This just came in the mail from the program committee chair, David Kirkpatrick; the official version should be up on the conference web site soon. Submissions are due December 2, with abstract due one week in advance.

The program committee includes my ex-student Erin Chambers, my academic sibling Nina Amenta, Nina's and my PhD advisor Raimund Seidel, and Raimund's MS advisor David Kirkpatrick. It's like a family reunion! (I am so screwed.)

---

26th Annual Symposium on Computational Geometry (SoCG 2010)
June 13-16, 2010
Snowbird, Utah, USA
In cooperation with ACM SIGACT and SIGGRAPH
http://www.sci.utah.edu/socg2010/

The Twenty-sixth Annual Symposium on Computational Geometry will be held at Snowbird, Utah. We invite submissions of high-quality papers, videos, and multimedia presentations describing original research addressing computational problems in a geometric setting, in particular their algorithmic solutions, implementation issues, applications, and mathematical foundations.

The topics of the Symposium reflect the rich diversity of research interests in computational geometry. They are intended to highlight both the depth and scope of computational geometry, and to invite fruitful interactions with other disciplines. Topics of interest include, but are not limited to:

• design, analysis, and implementation of geometric algorithms and data structures; lower bounds on the computational complexity of geometric problems;
• mathematical, numerical, and algebraic issues arising in the formulation, analysis, implementation, and experimental evaluation of geometric algorithms and heuristics; discrete and combinatorial geometry; computational topology;
• novel algorithmic applications of geometry in computer graphics, geometric modeling, computer-aided design and manufacturing, scientific computing, geographic information systems, database systems, robotics, computational biology, machine learning, sensor networks, medical imaging, combinatorial optimization, statistical analysis, discrete differential geometry, theoretical computer science, graph drawing, pure mathematics, and other fields.

Important Dates

• November 23, 2009: Paper titles and (short) abstracts due
• December 02, 2009: Full submissions due (23:59, Honolulu time)
• February 15, 2010: Notification of acceptance/rejection of papers
• February, 19, 2010: Video and multimedia submissions due
• March 01, 2010: Notification of acceptance or rejection of video/multimedia submissions
• March 15, 2010: Camera-ready papers and video/multimedia abstracts due
• April 20, 2010: Final versions of video/multimedia presentations due
• June 13-16, 2010: Symposium at Snowbird, Utah

Local Arrangements Co-Chairs

• Valerio Pascucci (University of Utah)
• Suresh Venkatasubramanian (University of Utah)

---

CALL FOR PAPERS

We invite submissions of high-quality papers describing original research on geometric algorithms and data structures, their mathematical foundations and correctness, their implementation, and their applications.

The program committee explicitly encourages the submission of video or multimedia in support of submitted papers. Authors may wish to consider making a separate submission to the video/multimedia track (see the guidelines below). Papers and video/multimedia submissions will be reviewed separately; acceptance or rejection of one will not influence acceptance or rejection of the other.

Final versions of accepted papers will be published by ACM in the symposium proceedings. Proceedings will be distributed to symposium participants and will also be available from ACM for purchase or through the digital library. An author of each accepted paper will be expected to attend the Symposium and give a presentation (approximately 20 minutes) of the paper. Authors of a selection of papers from the conference will be invited to submit extended versions of their papers to a special issue of one or more journals.

Paper Submission

All submissions should be made electronically; see the EasyChair SoCG2010 web pages http://www.easychair.org/conferences/?conf=socg2010 for detailed submission instructions. If electronic submission is not feasible, please contact the program committee chair, David Kirkpatrick <[email protected]>, well in advance of the submission deadlines.

Submission Guidelines

Papers should be submitted in the form of an extended abstract, which begins with the title of the paper, each author's name, affiliation, and e-mail address. This should be followed by a precise statement of the problem considered, a succinct summary of the results obtained (emphasizing the significance, novelty, and potential impact of the research), and a clear comparison with related work. The remainder of the extended abstract should provide sufficient detail to allow the program committee to evaluate the validity, quality, and relevance of the contribution. Clarity of presentation is very important; the whole extended abstract should be written carefully, taking into consideration that it will be read and evaluated by both experts and non-experts, often under tight time constraints.

Submissions should be typeset in single column format, using 11-point or larger font, with at least 1 inch/2.54 cm margins and single line spacing. Excluding the title page and bibliography, the extended abstract must not exceed 10 pages. Submissions deviating from these guidelines risk rejection without consideration of their merits.

A clearly marked appendix (of reasonable length) containing additional technical details may be included directly in the submission. Other supporting materials, such as an expanded version of the paper, a video or multimedia presentation, source code, or experimental data, may be provided by including a URL in the submission. Appendices and other supporting materials will not be regarded as part of the actual submission and will be considered only at the discretion of the program committee.

Authors must submit the title and a short abstract of their paper by November 23, 2009. This pre-submission will be used to help make program committee reading assignments. Extended abstracts must be received by December 2, 2009 (23:59, Honolulu time). There will be no extension of this deadline; late submissions will not be considered. Authors will be notified of acceptance or rejection by February 15, 2010. Final versions of accepted submissions will be due by March 15, 2010 for inclusion in the proceedings. The final proceedings papers must be formatted in accordance with ACM proceedings guidelines; LaTeX style files will be made available to authors of accepted papers.

Concurrent submission of the same (or essentially the same) abstract to SoCG and to another conference with published proceedings is not allowed. An extended abstract of a paper that is under journal review, or scheduled for publication in a journal after June 2010, may be submitted, when it is clear that the extended abstract differs substantially from the journal version. In such cases, the authors must include the journal version in an appendix that clearly identifies the status of the journal submission.

Program Committee

• Hee-Kap Ahn (POSTECH, Korea)
• Nina Amenta (University of California, Davis, USA)
• Tetsuo Asano (JAIST, Japan)
• Sergey Bereg (University of Texas at Dallas, USA)
• Therese Biedl (University of Waterloo, Canada)
• Robert Bridson (University of British Columbia, Canada)
• Erin Chambers (Saint Louis University, USA)
• Hazel Everett (University Nancy 2, France)
• Sandor Fekete (Braunschweig University of Technology, Germany)
• Efi Fogel (Tel Aviv University, Israel)
• David Kirkpatrick, Chair (University of British Columbia, Canada)
• Valentin Polishchuk (Helsinki Institute for Information Technology, Finland)
• Raimund Seidel (Saarland University, Germany)
• Bettina Speckmann (TU Eindhoven, The Netherlands)
• Csaba Toth (University of Calgary, Canada)
• Chee Yap (Courant Institute, NYU, USA)

---

CALL FOR VIDEO AND MULTIMEDIA PRESENTATIONS
19th Annual Video/Multimedia Review of Computational Geometry

Video and multimedia presentations are sought for the 19th Annual Video and Multimedia Review of Computational Geometry. This review showcases the use of visualization in computational geometry for exposition and education, for the visual exploration of geometry in research, and as an interface and a debugging tool in software development. Algorithm animations, visual explanations of structural theorems, descriptions of applications of computational geometry, and demonstrations of software systems are all appropriate.

Three to five minutes is ideal for most animations and presentations of applications; eight minutes is the upper limit. Submissions of movie clips in QuickTime or MPEG-4 compressed formats (e.g., XviD or DivX version 6) are encouraged. For ease of sharing and viewing, we encourage (but it is not required) that each submission be uploaded to YouTube, and that the corresponding url be supplied along with the submission. Consider adding a subtitle track to movie clips. We also encourage submissions of Macromedia Flash, Java applets, and limited forms of other multimedia or software. These formats must come with a script that will allow them to be distributed in both interactive and canned QT or MPEG movie formats. In case of doubt, please email the Video and Multimedia Program chair. Some suggestions on making movie clips can be found at http://www.ams.sunysb.edu/~jsbm/SoCG10/video_suggestions.html.

Accepted video and multimedia presentations will have an abstract in the published conference proceedings; video/multimedia authors will have an opportunity to present their work at the conference during a dedicated video session. Accepted presentations will be available online in various formats in a web proceedings. (The 2009 video proceedings are available at http://www.computational-geometry.org/SoCG-videos/socg09video/.)

Video/Multimedia Submission

Video/multimedia submissions should be sent by e-mail to the Video/Multimedia committee chair, Joe Mitchell <[email protected]>, to arrive by 23:59, New York time, Friday, February 19, 2010.

The author(s) should submit a one or two-page description of the material shown in the presentation, and where applicable, the techniques used in the implementation. An email address of the corresponding author and a URL or ftp address where the supporting materials can be retrieved must be included. The final two-page descriptions must be formatted according to the guidelines for ACM proceedings; LaTeX style files will be provided to authors of accepted presentations.

We explicitly encourage video/multimedia submissions that support papers submitted to the symposium. Submitted papers and associated video/multimedia submissions will be treated entirely separately by the respective committees: acceptance or rejection of one will not influence acceptance or rejection of the other.

Authors will be notified of acceptance or rejection, and given reviewers' comments by March 1, 2010. For each accepted submission, the final version of the 2-page textual description will be due by March 15, 2010 (electronically) for inclusion in the proceedings. Final versions of accepted video/multimedia presentations will be due April 20, 2010 in the best format available.

Video and Multimedia Presentation Program Committee

• Tamal Dey (Ohio State University)
• David Eppstein (UC Irvine)
• Jie Gao (Stony Brook)
• David Gu (Stony Brook)
• George Hart (Stony Brook)
• Joe Mitchell, Chair (Stony Brook)
• Jonathan Shewchuk (UC Berkeley)
• Monique Teillaud (INRIA Sophia Antipolis - Méditerrané)

---

SOCG Steering Committee (2009-2012)

• Jack Snoeyink, Chair (University of North Carolina)
• Mark de Berg, Secretary (TU Eindhoven)
• Joe Mitchell (SUNY Stony Brook)
• Günter Rote (FU Berlin)
• Monique Teillaud (INRIA Sophia Antipolis - Méditerrané)

Computational geometry at FOCS, part 2, plus true rumors

Here are a couple more computational geometry highlights from yesterday's FOCS schedule.

• Ankur Moitra and Tom Leighton solved the greedy embedding conjecture for 3-connected planar graphs, posed by Papadimitriou and Ratajczak in 2004. A path in the plane is distance-decreasing if the distance to one endpoint is monotonically decreasing as we walk along the path from the other endpoint. An embedding of a graph in the plane is greedy if every pair of nodes in the graph is connected by a distance-decreasing path. Papadimitriou and Ratajczak conjectured that every 3-connected planar graph has a greedy embedding. 3-connected planar graphs have tons of lovely geometric properties via theorems of Cauchy, Tutte, Steinitz, Koebe-Andreev-Thurston, and others, none of which proved useful in Moitra and Leighton's solution! Instead, they argue that any 3-connected planar graph (in fact, any circuit graph) has a spanning Christmas cactus, a subgraph in which every edge belongs to at most one cycle and deleting any vertex leaves at most two components, and then show how to greedily embed any Christmas cactus.

• Tasos Sidiropoulos described inapproximability resuls for metric embeddings into R^d, which he developed with Jiri Matousek. Given an n-point metric space M and a target dimension d, it is natural to ask for the minimum-distortion embedding of M into Euclidean d-space. Unfortunately, even for the case d=1, approximating the minimum distortion to small polynomial factors is NP-hard. Tasos and Jirka bootstrapped this known result to arbitrary dimensions, using a lovely product construction. If M is a bad example for embeddng into the line, then MxS is a bad example for embedding into R^d, where S is a sufficiently dense net on the (d-1)-sphere. Each copy of S must be embedded on an approximate sphere. A clever cohomology argument (hooray for Poincaré-Alexander duality!) then implies that these quasi-spheres are properly nested, which implies that the distortion is at least as bad as the distortion of M into the line. Thus result implies that random projection not only gives near-optimal worst-case distortion, but it also gives a nearly optimal approximation of the distortion for any metric space.

---

On our way to dinner last night, Mihai Patrascu asked me if the stories about my faculty job interview at MIT were true. Apparently, I impressed somebody (Mihai wouldn't say who) enough to become a cautionary example to MIT theory students. The story has become a little distorted over the last ten years, but yes, the essential details are accurate.

For any students entering the academic job market, who desperately want to avoid an offer from MIT, let me offer the following script, which proved wildly successful for me:

Gerry Sussman:

What's going to be the most important development in computer science in the next 20 years?

Yours truly:

I don't know, and neither does anyone else!

For extra added bonus points, make sure your tone of voice conveys just how incredibly stupid you think the question is.

I'm not crazy enough to think that was the only reason MIT didn't hire me—truthfully, I think they made the right decision—but it certainly didn't help. On the other hand, aside from a few added details about high school students and pornography, I'm not sure my answer would be much different today.