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

  Qries       Qries       Qries

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.

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.

Address

Visualization, Algorithms and Geometry (VGA) Lab
374 Thorvaldson Bldg
110 Science Place
University of Saskatchewan
Saskatoon, SK, Canada S7N 5C9

Phone Number

+1 306 966 6477

University of Saskatchewan, Saskatoon, SK, Canada