Invited Speakers

Daniela Rus, MIT
9:45 - 10:45, Wednesday, June 15.
Toward Pervasive Robots
Abstract: [+]
The digitization of practically everything coupled with the mobile Internet, the automation of knowledge work, and advanced robotics promises a future with democratized use of machines and wide-spread use of robots and customization. However, pervasive use of robots remains a hard problem. Where are the gaps that we need to address in order to advance toward a future where robots are common in the world and they help reliably with physical tasks? What is the role of geometric reasoning along this trajectory?
In this talk I will discuss challenges toward pervasive use of robots and recent developments in geometric algorithms for customizing robots. I will focus on a suite of geometric algorithms for automatically designing, fabricating, and tasking robots using a print-and-fold approach. I will also describe how geometric reasoning can play a role in creating robots more capable of reasoning in the world. By enabling on-demand creation of programmable robots, we can begin to imagine a world with one robot for every physical task.

Jacob Fox, Stanford.
11:55 - 12:55, Friday, June 17.
Discrete Geometry, Algebra, and Combinatorics
Abstract: [+]
Many problems in discrete and computational geometry can be viewed as finding patterns in graphs or hypergraphs which arise from geometry or algebra. Famous Ramsey, Turán, and Szemerédi-type results prove the existence of certain patterns in graphs and hypergraphs under mild assumptions. We survey recent results which show much stronger/larger patterns for graphs and hypergraphs that arise from geometry or algebra. We further discuss whether the stronger results in these settings are due to geometric, algebraic, combinatorial, or topological properties of the graphs.

Accepted Papers (with abstracts)

Link to list
(for the schedule, please see the program page)

Program Committee

Mohammad Ali Abam, Sharif University, Iran
Nina Amenta, University of California at Davis, USA
Ulrich Bauer, TU Munich, Germany
Sergio Cabello, University of Ljubljana, Slovenia
Jean Cardinal, Université Libre de Bruxelles, Belgium
Éric Colin de Verdière, École normale supérieure, Paris and CNRS, France
Sándor Fekete, (co-chair) TU Braunschweig, Germany
Marc Glisse, Inria, France
David Gu, Stony Brook University, USA
Matias Korman, Tohoku University, Japan
Anna Lubiw, (co-chair) University of Waterloo, Canada
Wolfgang Mulzer, FU Berlin, Germany
Joseph O'Rourke, Smith College, USA
Jeff M. Phillips, University of Utah, USA
Micha Sharir, Tel Aviv University, Israel
Takeshi Tokuyama, Tohuku University, Japan
Géza Tóth, Rényi Institute, Hungary
Kevin Verbeek, TU Eindhoven, Netherlands
Yusu Wang, Ohio State University, USA
Emo Welzl, ETH Zurich, Switzerland
Chee Yap, New York University, USA

Call for Papers

The 32nd International Symposium on Computational Geometry will be held in Boston, MA, as part of Computational Geometry Week. SoCG will be collocated with the 48th Symposium on the Theory of Computing (STOC), which will be held June 18-21, 2016. Making use of this collocation, it is intended to hold joint workshops with STOC (at the conference hotel of STOC) on June 18, and coordinate other aspects of the program where appropriate.

We invite submissions of high-quality papers that describe original research on computational problems in a geometric setting, in particular their algorithmic solutions, implementation issues, applications, and mathematical foundations. The program committee intends to interpret the scope of the conference broadly, and will seriously consider all papers that are of significant interest to the computational geometry research community.

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

Nov 27, 2015: Abstracts due (at most 300 words) (23:59, UTC-9)
Dec 04, 2015: Papers due (23:59, UTC-9)
Feb 12, 2016: Notification of acceptance/rejection of papers
Mar 24, 2016: Final versions of accepted papers due
Apr 1, 2016: Applications for student/postdoc support due
Jun 14-17, 2016: Symposium in Boston

There will be no extension of abstract and paper submission deadlines; late submissions will not be considered.

Publication and Awards

Final versions of accepted papers will be published by LIPIcs (Leibniz International Proceedings in Informatics) in the symposium proceedings. 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 special issues of "Discrete and Computational Geometry" and "Journal of Computational Geometry". There will be a best paper award. A best student presentation award will also be given based on the quality of the presentation by a student during the conference.

Paper Submission Guidelines

Submissions must be formatted in accordance with the LIPIcs proceedings guidelines and not exceed 15 pages including title-page and references, but possible excluding a clearly marked appendix (further described below). LIPIcs typesetting instructions can be found at and the lipics.cls LaTeX style at Final proceedings versions of accepted papers must be formatted using the same rules but without the appendix. See for the proceedings of 2015. Submissions deviating from the above guidelines will be rejected without consideration of their merits.

In order to encourage submission from both theory and practice, authors should clearly identify the main merits of the paper by choosing one of the following categories.
(T) Contributions to the theory of computational geometry
(P) Contributions to practical aspects of computational geometry
(B) Contributions to both theory and practice
There is no preassigned quota and there will not be separate tracks; the only purpose is to help the PC in focusing on the main strengths of papers. Authors should assign these categories by checking one or two of the appropriate boxes on the easychair submission page.

After the title, authors and abstract, the main body of the submission 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 submission 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 submission 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. All details needed to convince the Program Committee of the validity of the results should be provided, and supporting materials (including proofs of theoretical claims and experimental details) that do not fit in the 15-page limit should be given in an appendix. The appendix should not be a full version of the paper. It will be read by the program committee members at their discretion and will not be published as part of the proceedings. Thus, the submission should be able to stand on its own when references to the appendix are deleted or replaced by references to an extended version of the paper. If an appendix was used at the time of submission, authors are strongly encouraged to post a full version of their paper on some online repository (such as the arXiv) after acceptance.

Results previously published in another conference proceedings cannot be submitted. Simultaneous submissions of the results to another conference with published proceedings are not allowed. Exempted are workshop or conference handouts containing short abstracts. Results that have already been accepted (with or without revision) for publication by a journal, at the time of their submission to the conference, will not be allowed. A paper submitted to a journal but not yet accepted to a journal can be submitted to the conference. In such cases, the authors must mention this in the submission appendix and clearly identify the status of the journal submission on November 27, 2015.

Submission Server

All submissions must be made electronically; see the EasyChair SoCG2016 web page for detailed submission instructions.