COVID-19 Update
The committee has made the decision to run the CCCG 2020 conference online. The decision is taken considering the novel coronavirus (COVID-19) situation and associated health and safety concerns.
About The Event
The 32nd Canadian Conference on Computational Geometry (CCCG 2020) will be held in Saskatoon, Saskatchewan, Canada on August 5-7, 2020, at the University of Saskatchewan. The Canadian Conference on Computational Geometry (CCCG) is a forum to disseminate and discuss new theoretical and applied results in discrete and computational geometry. CCCG focuses on the design of efficient algorithms, the development of software, and the study of the mathematical foundations of computational problems whose formulations involve geometric constraints. The field of computational geometry is motivated by problems from a broad range of application areas, as diverse as computer graphics and animation, computer vision, computer-aided design and manufacturing, geographic information systems, pattern recognition, wireless communications, robotics, protein folding, urban planning, graph drawing, or statistical analysis.
A pdf version of the call for paper is here.
A list of previous editions of CCCG.
Program Committee
Esther M. Arkin, Stony Brook Univ., USA Therese Biedl, Univ. of Waterloo, Canada Ahmad Biniaz, Univ. of Windsor, Canada Sergio Cabello, Univ. of Ljubljana, Slovenia Jean Cardinal, Univ. Libre de Bruxelles, Belgium Erin W. Chambers, Saint Louis University, USA Guilherme D. da Fonseca, Aix-Marseille Univ., France Mirela Damian, Villanova Univ., USA Vida Dujmović, Univ. of Ottawa, Canada Stephane Durocher, Univ. of Manitoba, Canada William Evans, Univ. of British Columbia, Canada Mark Keil (co-chair), Univ. of Saskatchewan, Canada Irina Kostitsyna, Eindhoven Univ. of Technology, Netherlands Anna Lubiw, Univ. of Waterloo, Canada Victor Milenkovic, Univ. of Miami, USA Tillmann Miltzow, Utrecht Univ., Netherlands Debajyoti Mondal (co-chair), Univ. of Saskatchewan, Canada Pat Morin, Carleton Univ., Canada Amir Nayyeri, Oregon State Univ., USA Joseph O'Rourke, Smith College, USA Rodrigo I. Silveira, Univ. Politècnica de Catalunya, Spain Csaba D. Tóth, California State Univ. Northridge, USA Ryuhei Uehara, JAIST, Japan Norbert Zeh, Dalhousie Univ., Canada
Submission Details
Authors are invited to submit papers describing original research of theoretical or practical significance in computational, combinatorial and discrete geometry, as well as related areas. Submissions will be refereed by the Program Committee. Submissions should not exceed six pages, excluding references and appendices. Documents must be prepared using LaTeX; the appropriate template is available from the link below. Authors who feel that additional details are necessary should include a clearly marked appendix, which will be read at the discretion of the Program Committee. Only electronic submissions via EasyChair (link below) will be accepted. Simultaneous submission to another conference or journal is not allowed. Accepted papers are expected to be presented at the conference. Failure to do so will result in removal of the paper from the proceedings. Proceedings will be published online. There will be no paper proceedings. Authors of selected papers will be invited to submit extended versions to a special issue of the journal Computational Geometry: Theory and Applications.
Important Dates
Submissions Due: April 20, 2020 May 10, 2020 (23:59 Anywhere on Earth)
Paper Notification: May 31, 2020 June 20, 2020 (23:59 Anywhere on Earth)
Prerecorded Videos Due: July 10, 2020 (23:59 Anywhere on Earth)
Final Versions Due: June 30, 2020 July 31, 2020 (23:59 Anywhere on Earth)
Conference: August 5-7, 2020
Submission Link
Submissions are accepted via Easychair Submission System.
Paper Template
Download the CCCG 2020 paper template.
Social Media
Follow us on Facebook.
Sponsors
Keynote Speakers
'Tribute to Godfried Toussaint' - by Erik Demaine
Over three decades ago, Godfried Toussaint (1944-2019) cofounded the Canadian
Conference on Computational Geometry. As a father to the conference and the
field in general, his impact and influence was immense. In his honor, I will
talk about some of my favorite research that he and I did together, including
several past CCCG papers. Possible topics include:
* Godfried's only paper with a counterexample to his own work
* Geometry of musical rhythm, with connections to Euclid's GCD algorithm
* Geometry of sand drawing (ethnomathematics), with some new updates presented here at CCCG 2020
* Machine learning through Voronoi diagrams
* Untangling linkages
* Classic computational geometry, such as guarding polyhedra and polyhedronizing point sets
* Godfried's supercollaborative model of doing research
'Chasing Puppies' - by Jeff Erickson
I will describe a topological solution to the following puzzle, which Michael Biro posed as an open problem at CCCG 2013. A human and a puppy find themselves at different points on a walking trail, which is a simple closed curve in the plane. The human and puppy can see each other from anywhere on the trail, but they cannot leave the trial. The puppy always moves as quickly as possible to decrease its distance to the human. Can the human catch the puppy? (Yes!)
This is joint work with Irina Kostitsyna, Maarten Löffler, Tillman Miltzow, Jérôme Urhausen, and Jordi Vermeulen.
'Topological and geometric methods for graph analysis' - by Yusu Wang
In recent years, topological and geometric data analysis (TGDA) has emerged as a new and promising field for processing, analyzing and understanding complex data. Indeed, geometry and topology form natural platforms for data analysis, with geometry describing the ''shape'' and ''structure'' behind data; and topology characterizing / summarizing both the domain where data are sampled from, as well as functions and maps associated to them.
In this talk, I will show how topological and geometric ideas can be used to analyze graph data, which occurs ubiquitously across science and engineering. Graphs could be geometric in nature, such as road networks in GIS, or relational and abstract. I will particularly focus on the reconstruction of hidden geometric graphs from noisy data, as well as graph matching and classification. I will discuss the motivating applications, algorithm development, and theoretical guarantees for these methods. Through these topics, I aim to illustrate the important role that geometric and topological ideas can play in data analysis.
Accepted Papers
| . |
|---|
| Sariel Har-Peled and Mitchell Jones. Some Geometric Applications of Anti-Chains |
| Davood Bakhshesh and Mohammad Farshi. A Degree 3 Plane $5.19$-Spanner for Points in Convex Position |
| Tonan Kamata, Akira Kadoguchi, Takashi Horiyama and Ryuhei Uehara. Efficient Folding Algorithms for Regular Polyhedra |
| Joseph O'Rourke. Vertex-Transplants on a Convex Polyhedron |
| Anil Maheshwari, Saeed Mehrabi, Sasanka Roy and Michiel Smid. Covering Points with Concentric Objects |
| Abrar Kazi and Michiel Smid. Closest-Pair Queries and Minimum-Weight Queries are Equivalent for Squares |
| Christian Scheffer. Scheduling Three Trains is NP-Complete |
| Haitao Wang and Yiming Zhao. A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space |
| Ovidiu Daescu and Ka Yaw Teo. Characterization and Computation of Feasible Trajectories for an Articulated Probe with a Variable-Length End Segment |
| Georgiy Klimenko, Benjamin Raichel and Gregory Van Buskirk. Sparse Convex Hull Coverage |
| Hongyao Huang and Benjamin Raichel. Convex Hull Complexity of Uncertain Points |
| Jared Coleman, Evangelos Kranakis, Oscar Morales-Ponce, Jaroslav Opatrny, Jorge Urrutia and Birgit Vogtenhuber. Minimizing The Maximum Distance Traveled To Form Patterns With Systems of Mobile Robots |
| Mark Keil, Debajyoti Mondal and Ehsan Moradi. Finding a Maximum Clique in a Grounded 1-Bend String Graph |
| Maike Buchin and Bernhard Kilgus. Frechet Distance Between Two Point Sets |
| Mansoor Davoodi, Hosein Enamzadeh and Ashkan Safari. Path Planning in a Weighted Planar Subdivision Under the Manhattan Metric |
| Siu-Wing Cheng, Otfried Cheong and Taegyoung Lee. Fitting a Graph to One-Dimensional Data |
| Ben Chugg, William S. Evans and Kelvin Wong. Simultaneous Visibility Representations of Undirected Pairs of Graphs |
| Jonathan Lenchner and Eli Packer. Line Segment Visibility: Theoretical and Experimental Results |
| Erik D. Demaine, Martin L. Demaine and David Eppstein. Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra |
| Ming Ouyang. Parallel topological sweep |
| David Eppstein. Dynamic Products of Ranks |
| Alejandro Flores-Velazco. Social Distancing is Good for Points too! |
| Kristin DeSplinter, Satyan Devadoss, Jordan Readyhough and Bryce Wimberly. Nets of higher-dimensional cubes |
| Frederik Jensen, Aadi Joshi and Saurabh Ray. Discrete Helly type theorems |
| Neeldhara Misra, Harshil M. and Aditi Sethia. Red-Blue Point Separation for Points on a Circle |
| Hugo Akitaya, Erik D. Demaine, Jason S. Ku, Jayson Lynch and Csaba D. Tóth. 2048 Without Merging |
| Ovidiu Daescu and Hemant Malik. City Guarding with Limited Field of View |
| Daniel Lokshtanov, Chinmay Sonar, Subhash Suri and Jie Xue. Fair Covering of Points by Balls |
| Kirk Gardner and Don Sheehy. A Simple Algorithm for kNN Sampling in General Metrics |
| Ahmad Biniaz and Zhikai Lin. Minimum Ply Covering of Points with Convex Shapes |
| Erik D. Demaine, Martin L. Demaine, David Eppstein and Joseph O'Rourke. Some Polycubes Have No Edge Zipper Unfolding |
| Gábor Damásdi and Dömötör Pálvölgyi. Realizing m-uniform four-chromatic hypergraphs with disks |
| Man-Kwun Chiu, Erik D. Demaine, Yevhenii Diomidov, David Eppstein, Robert A. Hearn, Adam Hesterberg, Matias Korman, Irene Parada and Mikhail Rudoy. New Results in Sona Drawing: Hardness and TSP Separation |
| Vincent Despre, Michaël Rao and Stéphan Thomassé. Testing Balanced Splitting Cycles in Complete Triangulations |
| Prosenjit Bose, Paz Carmi, Stephane Durocher, Shahin Kamali and Arezoo Sajadpour. Non-Crossing Matching of Online Points |
| Hsien-Chih Chang and Tim Ophelders. Planar Emulators for Monge Matrices |
| Don Sheehy. One-Hop Greedy Permutations |
| Omid Gheibi and Hamid Zarrabi-Zadeh. Blind Voronoi Game |
| Sergey Bereg and Mohammadreza Haghpanah. Computing the Caratheodory Number of a Point |
| Kyle Clarkson and Will Evans. External Exploration of a Convex Polygon |
| David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller and Tim Wylie. Relocating Units in Robot Swarms with Uniform Control Signals is PSPACE-Complete |
| David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller and Tim Wylie. Building Patterned Shapes in Robot Swarms with Uniform Control Signals |
| Péter Ágoston. A lower bound on the number of colours needed to nicely colour a sphere |
| Kevin Buchin, Herman Haverkort and Hidde Koerts. Restricted-Weight Minimum-Dilation Spanners on Three Points |
| Kingston Yao Czajkowski, Erik D. Demaine, Martin L. Demaine, Kim Eppling, Robby Kraft, Klara Mundilova and Levi Smith. Folding Small Polyominoes into a Unit Cube |
| Benjamin Holmgren, Brittany Fasy, David Millman and Bradley McCoy. If You Must Choose Among Your Children, Always Pick the Right One |
| Sima Hajiaghaei Shanjani. Hardness of Approximation for Red-Blue Covering |
Conference Program
Current Saskatoon Time
The CCCG 2020 Program is available here.
The CCCG 2020 Proceedings is available here.
Gallery
CCCG 2020 had over 170 registered participants. Here are some screenshots during the keynote talks and the business meeting!
Registration
CCCG 2020 will be an online conference with live keynote talks and parallel sessions. The pre-recorded video presentations will be available on the website on July 25, 2020. Enjoy the videos and send your questions for the presenters to cccg2020@easychair.org with the session name and paper title. You can also attend the session and ask your questions to the presenter!
Registration Deadline: August 4, 2020.
To register for the event please click here. (The tickets are currently sold out - please email to cccg2020@easychair.org if you want to register).
The registration is supported by Eventbrite. If the domain (https://www.eventbrite.com) is not available in your region, then please fill this form and email to us with the subject 'CCCG 2020 Registration Request'.
The details of the online platform will be emailed to the registered participants prior to the event.
