Distinguished Lecture
On Map Construction, Map Comparison, and Trajectory Clustering
Carola Wenk, Tulane University
Geo-referenced trajectory data is collected in a wide range of applications, such as for a variety of location-based services on street maps, hiking trail logging, and the study of social behavior in animals. This talk will cover different algorithms for aggregating trajectory data, in particular by constructing road maps. Road map construction is a type of geometric reconstruction problem in which the task is to extract the underlying geometric graph structure described by a set of movement-constrained trajectories, or in other words reconstruct a geometric domain that has been sampled with continuous curves that are subject to noise. Finally, different approaches for map comparison will be discussed, including signatures and distance measures.

Paul Erdős Memorial Lecture
Geometric problems and structures arising from the study of wireless networks
Matya Katz, Ben-Gurion University of the Negev
The study of wireless networks has motivated the formulation of interesting geometric optimization problems such as the power assignment problem, as well as the definition of new geometric data structures such as the bounded-angle spanning tree (related to networks with angular constraints) and the SINR diagram (induced by the Signal to Interference plus Noise Ratio equation). This talk will discuss some of these problems and structures, mentioning a few open problems along the way.

Ferran Hurtado Memorial Lecture
On Nonogram and Graph Planarity Puzzle Generation
Marc van Kreveld, Utrecht University
There are many puzzles in the world, both physical and digital ones. From the algorithms research perspective, a lot of attention has been given to combinatorial and graph-based puzzles and how to solve them. We will focus on puzzles with a geometric component and where techniques from discrete and computational geometry can be employed to generate them. Automated generation of puzzles is arguably more useful than automated solving. We will focus on new nonogram puzzles and new graph planarization puzzles, and encounter digitization of polygons, Hausdorff and Frechet distance, Bezier curves, simulated annealing, graph drawing, and order types.

Click here for the list of accepted papers

Click here for the full proceedings as one file


(Room 118 and the Robert B. Schultz Lecture Theatre are located in St. John's College. The Galleria is at the Robert B. Schultz Lecture Theatre. See the campus map.)

6:00 PM Welcome Reception (snacks only)
(at Degrees Restaurant, University Centre, 3rd Floor)

8:30 AM Breakfast (in the Galleria)
9:00 AM Welcome and Opening Address  
9:30 AM Paul Erdős Memorial Lecture - Matya Katz
Geometric Problems and Structures Arising from the Study of Wireless Networks
10:30 AM Refreshments (in the Galleria)
10:50 AM Session 1A
Session 1B
Low Ply Drawings of Trees and 2-Trees
(Timothy Johnson and Michael T. Goodrich)
Sto-Stone is NP-Complete
(Addison Allen and Aaron Williams)
11:10 AM The Crossing Number of Single-Pair-Seq-Shellable Drawings of Complete Graphs
(Lutz Oettershagen and Petra Mutzel)
A Paper on Pencils: A Pencil and Paper Puzzle: Pencils is NP-Complete
(Daniel Packer, Sophia White and Aaron Williams)
11:30 AM Learning Simplicial Complexes from Persistence Diagrams
(Robin Lynne Belton, Brittany Terese Fasy, Rostik Mertz, Samuel Micka, David L. Millman, Daniel Salinas, Anna Schenfisch, Jordan Schupbach and Lucia Williams)
Switches are PSPACE-Complete
(Jonathan Gabor and Aaron Williams)
11:50 AM Lunch (on your own)
1:30 PM Session 2A
Session 2B
Packing Plane Spanning Trees into a Point Set
(Ahmad Biniaz and Alfredo Garcı́a)
Away from Rivals
(Kazuyuki Amano and Shin-Ichi Nakano)
1:50 PM Compatible Paths on Labelled Point Sets
(Elena Arseneva, Yeganeh Bahoo, Ahmad Biniaz, Pilar Cano, Farah Chanchary, John Iacono, Kshitij Jain, Anna Lubiw, Debajyoti Mondal, Khadijeh Sheikhan and Csaba D. Toth)
An Efficient Approximation for
Point-set Diameter in Higher Dimensions

(Mahdi Imanparast, Seyed Naser Hashemi and Ali Mohades)

2:10 PM Ladder-Lottery Realization
(Katsuhisa Yamanaka, Takashi Horiyama, Takeaki Uno and Kunihiro Wasa)
Computing the Shift-Invariant Bottleneck Distance for Persistence Diagrams
(Don Sheehy, Oliver Kisielius and Nicholas Cavanna)
2:30 PM Refreshments (in the Galleria)
2:50 PM Session 3A
Session 3B
Hitting a Set of Line Segments with
One or Two Discrete Centers

(Xiaozhou He, Zhihui Liu, Bing Su, Yinfeng Xu, Feifeng Zheng and Binhai Zhu)
The Computational Complexity of Finding Hamiltonian Cycles in Grid
(Jayson Lynch and Kaiying Hou)
3:10 PM Finding Intersections of Algebraic Curves in a Convex Region using Encasement
(Joseph Masterjohn, Victor Milenkovic and Elisha Sacks)
Improved Bounds for the Traveling Salesman Problem with Neighborhoods
(Ioana Bercea)
3:30 PM Geometric Fingerprint Recognition via
Oriented Point-Set Pattern Matching

(David Eppstein, Michael Goodrich, Jordan Jorgensen and Manuel Torres)
Width and Bounding Box of Imprecise Points
(Vahideh Keikha, Maarten Löffler, Ali Mohades and Zahed Rahmati)
4:00 PM 30th CCCG Group Photo (meet in the Galleria)
4:10 PM Open Problem Session
Open problems from CCCG'17
5:30 PM Bus to Shaw Park (meet outside North entrance to St. John’s College)
7:00 PM Baseball game: Winnipeg Goldeyes vs. Cleburne Railroaders (at Shaw Park)
10:00 PM
(or when game ends)
Bus to University of Manitoba (meet outside Shaw Park)

8:30 AM Breakfast (in the Galleria)
9:00 AM Distinguished Lecture - Carola Wenk
On Map Construction, Map Comparison, and Trajectory Clustering
10:00 AM Refreshments (in the Galleria)
10:20 AM Session 4A
Session 4B
On the Coverage of Points in the Plane by
Disks Centered at a Line

(Logan Pedersen and Haitao Wang)
Unfolding Low-Degree Orthotrees with Constant Refinement
(Mirela Damian and Robin Flatland)
10:40 AM Composable Coreset for k-Center
in Doubling Metrics

(Sepideh Aghamolaei and Mohammad Ghodsi)
Dihedral Rigidity and Deformation
(Nina Amenta and Carlos Rojas)
11:00 AM Approximation Schemes for Covering and Packing in the Streaming Model
(Christopher Liaw, Paul Liu and Robert Reiss)
Vertex Unfoldings of Orthogonal Polyhedra
(Luis Garcia, Andres Gutierrez, Isaac Ruiz and Andrew Winslow)
11:20 AM Formigrams: Clustering Summaries
of Dynamic Data

(Woojin Kim and Facundo Memoli)
Approximate Free Space Construction and Maximum Clearance Path Planning for a Four Degree of Freedom Robot
(Chloe Arluck, Victor Milenkovic and Elisha Sacks)
11:40 AM Lunch (on your own)
1:30 PM Session 5A
Session 5B
Integral Unit Bar-Visibility Graphs
(Therese Biedl, Ahmad Biniaz, Veronika Irvine, Philipp Kindermann, Anurag Murty Naredla and Alexi Turcotte)
Red-Blue-Partitioned MST, TSP, and Matching
(Matthew P. Johnson)
1:50 PM Continuous Terrain Guarding
with Two-Sided Guards

(Wei-Yu Lai and Tien-Ruey Hsiang)
Optimal Solutions for a Geometric Knapsack Problem using Integer Programming
(Rafael Cano, Cid de Souza and Pedro de Rezende)
2:10 PM Finding Minimum Witness Sets
in Orthogonal Polygons

(Israel Aldana-Galván, Carlos Alegría-Galicia, José Luis Álvarez-Rebollar, Nestaly Marin-Nevárez, Erick Solís-Villarreal, Jorge Urrutia and Carlos Velarde)
Approximate Data Depth Revisited
(Rasoul Shahsavarifar and David Bremner)
2:30 PM Refreshments (in the Galleria)
2:50 PM Session 6A
Session 6B
Approximate Range Closest-pair Search
(Jie Xue, Yuan Li and Ravi Janardan)
Distance-Two Colorings of Barnette Graphs
(Tomas Feder, Pavol Hell and Carlos Subi)
3:10 PM Time-Dependent Shortest Path Queries
Among Growing Discs

(Arash Nouri, Anil Maheshwari and Jörg-Rüdiger Sack)
Emanation Graph: A New t-Spanner
(Bardia Hamedmohseni, Zahed Rahmati and Debajyoti Mondal)
3:30 PM Trajectory Planning for an Articulated Probe
(Ovidiu Daescu, Kyle Fox and Ka Yaw Teo)
Uniform 2D-Monotone Minimum Spanning Graphs
(Konstantinos Mastakas)
3:50 PM Refreshments (in the Galleria)
4:00 PM Business Meeting  
4:45 PM Bus to Canadian Museum for Human Rights
(meet outside North entrance to St. John’s College)
5:30 PM Guided Museum Tour (90 mins) or visit The Forks on your own
7:00 PM Cocktails and Hors d’Oeuvres (at Canadian Museum for Human Rights)
7:30 PM Banquet Dinner (at Canadian Museum for Human Rights)
9:30 PM Bus to University of Manitoba (meet outside museum)

8:30 AM Breakfast (in the Galleria)
9:00 AM Ferran Hurtado Memorial Lecture - Marc van Kreveld
On Nonogram and Graph Planarity
Puzzle Generation
10:00 AM Refreshments (in the Galleria)
10:20 AM Session 7A
Session 7B
Threadable Curves
(Joseph O'Rourke and Emmely Rogers)
Some Heuristics for the
Homological Simplification Problem

(Erin Chambers, Tao Ju, David Letscher, Mao Li, Christopher Topp and Yajie Yan)
10:40 AM Looking for Bird Nests:
Identifying Stay Points with Bounded Gaps

(Ali Gholami Rudi)
Isomorphism Elimination by Zero-Suppressed Binary Decision Diagrams
(Takashi Horiyama, Masahiro Miyasaka and Riku Sasaki)
11:00 AM When Can We Treat Trajectories as Points?
(Parasara Duggirala and Don Sheehy)
On Error Representation in Exact-decisions Number Types
(Martin Wilhelm)
11:20 AM Compatible 4-Holes in Point Sets
(Ahmad Biniaz, Anil Maheshwari and Michiel Smid)   

11:40 AM End of Conference