You are now in the main content area

TBA

Program

Last update: August 29

Complete proceedings can be found PDF filehere, opens in new window.

First column, scheduled in ENG103, and second in ENG102.

We will hold registration with the welcome reception.

There will be also registration starting at 8:30am on Day 1, 2 and 3.

Continental breakfast will be available everyday outside ENG103 at 8:30am.

Attention: Make sure to enter ENG building from Church St entrance.

Map to ENG, external link, opens in new window

 

August 24:

Reception is at 6-8pm on August 24.

Drinks and snacks will be served.

Location: International room, International Living/Learning Centre (ILC)

240 Jarvis St, Toronto, ON M5B 2L1

Map, external link, opens in new window

Attention: Make sure to enter from Jarvis St entrance.

August 25:

  ENG103 ENG102
8:50am-9:20am
Welcome remarks  
9:20am-10:20am

Paul Erdős Memorial Lecture

Keynote presentation:

Particle Systems, Geometry, and Dynamic Networks

By Bernard Chazelle

 
10:20am-10:35am Coffee break  
10:35am-11:35am

Chair: Victor Milenkovic  

1. PDF fileMinimum Enclosing Spherical/Cylindrical Shells in High-Dimensional Streams, opens in new window
Authors: Mohammad Javad Eslami-Bidgoli and Hamid Zarrabi-Zadeh

2. PDF fileFast Deterministic Approximation of Medoid in Rd, opens in new window
Authors: Ovidiu Daescu and Ka Yaw Teo.  

3. PDF fileBudgeted Steiner Networks: Three Terminals with Equal Path Weights, opens in new window
Authors: Jingjin Yu and Mario Szegedy

Chair: Carlos Seara

1. PDF fileBurning Number for the Points in the Plane, opens in new window
Authors: Mark Keil, Debajyoti Mondal and Ehsan Moradi.

2. PDF fileComputing Batched Depth Queries and the Depth of a Set of Points, opens in new window
Authors: Stephane Durocher, Alexandre Leblanc and Sachini Rajapakse

3. PDF fileOn the Geometry of Stable Steiner Tree Instances, opens in new window
Authors: James Freitag, Neshat Mohammadi, Aditya Potukuchi and Lev Reyzin

11:35am-1:30pm Lunch break (on your own)  
1:30pm-2:30pm

Chair: Aditya Potukuchi

1. PDF fileUniformly Monotone Partitioning of Polygons Revisited, opens in new window
Authors: Hwi Kim, Jaegun Lee and Hee-Kap Ahn


2. PDF fileApproximating Convex Polygons by Histogons, opens in new window
Authors: Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon and Hee-Kap Ahn

3. PDF fileQuasi-Twisting Convex Polyhedra, opens in new window
Authors: Joseph O'Rourke, Anna Lubiw, Ryuhei Uehara, Chie Nara, Thomas Hull, Klara Mundilova and Josef Tkadlec

Chair: Ovidiu Daescu

1. PDF fileDrawing complete outer-1-planar graphs in linear area, opens in new window
Author: Therese Biedl

2. PDF fileOn the Biplanar and k-Planar Crossing Numbers, opens in new window
Authors: Alireza Shavali and Hamid Zarrabi-Zadeh

3. PDF fileA Sub-quadratic Algorithm for the Proximity Connected k-center Problem on Paths via Modular Arithmetic, opens in new window
Authors: Amirhossein Mozafari, Binay Bhattacharya and Tsunehiko Kameda

2:30pm-2:45pm Coffee break  
2:45pm-3:45pm

Chair: Konstantinos Georgiou

1. PDF fileDiverse Non Crossing Matchings, opens in new window
Authors: Neeldhara Misra, Harshil M. and Saraswati Nanoti

2. PDF fileHigh-Dimensional Axis-Aligned Bounding Box with Outliers, opens in new window         
Authors: Ali Mostafavi and Ali Hamzeh

3. PDF fileUnfolding Some Classes of One-Layer Polycubes, opens in new window
Author: Josef Minařík

Chair: Therese Biedl

1. PDF fileZHED is NP-complete, opens in new window
Authors: Sagnik Saha and Erik D. Demaine

2. PDF fileUnstacking Slabs in Megalit is NP-Hard, opens in new window
Authors: Kirby Gordon, Jacob Lezberg and Aaron Williams

3. PDF fileThe Median Line Segment Problem: Computational Complexity and Constrained Variants, opens in new window
Authors: Ovidiu Daescu and Ka Yaw Teo

3:45pm-4:15pm Coffee break (group photo*)  
4:15pm-5:15pm

Chair: Joseph O'Rourke

Open problem sessions

 
7:00pm-9:00pm Pub Night**  

*Location: TMU building; SLC (Sheldon & Tracy Levy Student Learning Centre)
341 Yonge St, M5B 1S1

Map, external link, opens in new window

**Location: Duke of York
39 Prince Arthur Avenue, M5R 1B2
Light snacks and Drinks

Map, external link, opens in new window

August 26:

  ENG103 ENG102
9am-10am

Godfried Toussaint Memorial Lecture

Keynote presentation:

Obstacle Avoidance

By Subhash Suri

 
10am-10:15am Coffee break  
10:15am-11:35am

Chair: Joseph O’Rourke

1. PDF fileWeighted shortest path in equilateral triangular meshes, opens in new window
Authors: Prosenjit Bose, Guillermo Esteban and Anil Maheshwari

2. PDF fileComputational Complexity of One-Dimensional Origami and Its Application to Digital Signature, opens in new window
Authors: Junnosuke Hoshido, Tonan Kamata, Tsutomu Ansai and Ryuhei Uehara

3. PDF fileDiscretization to Prove the Nonexistence of "Small" Common Unfoldings Between Polyhedra, opens in new window
Authors: Elena Arseneva, Erik D. Demaine, Tonan Kamata and Ryuhei Uehara

4. PDF fileComputational Complexity of Flattening Fixed-Angle Orthogonal Chains, opens in new window
Authors: Erik D. Demaine, Hiro Ito, Jayson Lynch and Ryuhei Uehara

Chair: David Mount

1. PDF fileGlobally linked pairs in braced maximal outerplanar graphs, opens in new window
Authors: Dániel Garamvölgyi and Tibor Jordan

2. PDF fileEfficient Graph Reconstruction and Representation Using Augmented Persistence Diagrams, opens in new window
Authors: Anna Schenfisch, Brittany Terese Fasy, Samuel Micka, David L. Millman and Lucia Williams.  

3. PDF fileOptimally Tracking Labels on an Evolving Tree, opens in new window
Authors: Aditya Acharya and David Mount

4. PDF fileA 13/9-approximation of the average-2π/3-MST, opens in new window
Authors: Ahmad Biniaz, Prosenjit Bose and Patrick Devaney

11:35am-1:30pm Lunch break (on your own)  
1:30pm-2:30pm

Chair: Jan Vahrenhold

1. PDF fileCurve Stabbing Depth: Data Depth for Plane Curves, opens in new window
Authors: Stephane Durocher and Spencer Szabados

2. PDF fileUsing Existential Theory of the Reals to Bound VC Dimension, opens in new window
Authors: Austin Watkins and Jeff Phillips

3. PDF fileA Constant Time Algorithm for Solving Simple Rolling Cube Mazes, opens in new window
Authors: Randal Tuggle, Davis Murphy and Nicholas Lorch

 

Chair: Debajyoti Mondal   

1. PDF fileOrthogonal Dissection into Few Rectangles, opens in new window
Author: David Eppstein

 

2. PDF fileEfficient Predicate Evaluation using Statistical Degeneracy Detection, opens in new window
Authors: Victor Milenkovic and Elisha Sacks

3. PDF fileLocked and Unlocked Smooth Embeddings of Surfaces, opens in new window
Author: David Eppstein

 

2:30pm-2:45pm Coffee break  
2:45pm-3:45pm

Chair: Erik Krohn

1. PDF fileOptimally Confining Lattice Polymers, opens in new window
Authors: Robert Barish and Tetsuo Shibuya

2. PDF fileMaximum Subbarcode Matching and Subbarcode Distance, opens in new window
Author: Oliver Chubet

3. PDF fileDiamonds are Forever in the Blockchain: Geometric Polyhedral Point-Set Pattern Matching, opens in new window
Authors: Gill Barequet, Shion Fukuzawa, Michael Goodrich, David Mount, Martha Osegueda and Evrim Ozel

Chair: Stephane Durocher

1. PDF fileA Randomized Algorithm for Non-crossing Matching of Online Points, opens in new window
Authors: Shahin Kamali, Pooya Nikbakht and Arezoo Sajadpour.


2. PDF fileEfficiently Enumerating Scaled Copies of Point Set Patterns, opens in new window
Authors: Aya Bernstine and Yehonatan Mizrahi

3. PDF fileOnline Square Packing with Rotation, opens in new window
Authors: Shahin Kamali and Pooya Nikbakht

3:45pm-4pm
Coffee break  
4pm-5pm

Chair: Stephane Durocher

Business meeting

 
6pm-9pm Banquet dinner***  

***Location: International room, International Living/Learning Centre (ILC), 240 Jarvis St, M5B 2L1

Map, external link, opens in new window

Make sure to enter from Jarvis St entrance.

August 27:

  ENG103 ENG102
9am-10am

Ferran Hurtado Memorial Lecture

 

Keynote presentation:

Art Gallery Problems

By Jorge Urrutia

 

 
10am-10:15am Coffee break  
10:15am-11:15am

Chair: Jie Xiao

1. PDF fileOpposing Half Guards, opens in new window
Authors: Erik Krohn, Bengt J. Nilsson and Christiane Schmidt

2PDF file. Reflections in an Octagonal Mirror Maze, opens in new window
Author: David Eppstein

3. PDF fileComputing Realistic Terrains from Imprecise Elevations, opens in new window
Authors: Anna Lubiw and Graeme Stroud

Chair: Ryuhei Uehara

1. PDF fileQuantitative Helly-type Hypergraph Chains, opens in new window
Author: Attila Jung

2. PDF fileA Theory of Spherical Diagrams, opens in new window
Author: Giovanni Viglietta

3. PDF fileMaximum Weight Convex Polytope, opens in new window
Authors: Ali Mohammad Lavasani, Denis Pankratov and Mohammad Ali Abam

11:15am-11:30am Coffee break  
11:30am-11:50am

Best student paper presentation:

PDF fileA bound for Delaunay flip algorithms on flat tori, opens in new window
Author: Loïc Dubois

 
11:50am Closing remarks, end of conference
 

Accepted papers

  • Ali Mostafavi and Ali Hamzeh. “High-Dimensional Axis-Aligned Bounding Box with Outliers”
  • Oliver Chubet. “Maximum Subbarcode Matching and Subbarcode Distance”
  • James Freitag, Neshat Mohammadi, Aditya Potukuchi and Lev Reyzin. “On the Geometry of Stable Steiner Tree Instances”
  • Jingjin Yu and Mario Szegedy. “Budgeted Steiner Networks: Three Terminals with Equal Path Weights”
  • Junnosuke Hoshido, Tonan Kamata, Tsutomu Ansai and Ryuhei Uehara. “Computational Complexity of One-Dimensional Origami and Its Application to Digital Signature”
  • Sagnik Saha and Erik D. Demaine. “ZHED is NP-complete”
  • Elena Arseneva, Erik D. Demaine, Tonan Kamata and Ryuhei Uehara. “Discretization to Prove the Nonexistence of "Small" Common Unfoldings Between Polyhedra”
  • Austin Watkins and Jeff Phillips. “Using Existential Theory of the Reals to Bound VC Dimension”
  • Randal Tuggle, Davis Murphy and Nicholas Lorch. “A Constant Time Algorithm for Solving Simple Rolling Cube Mazes”
  • Loïc Dubois. “A bound for Delaunay flip algorithms on flat tori”
  • Erik Krohn, Bengt J. Nilsson and Christiane Schmidt. “Opposing Half Guards”
  • Attila Jung. “Quantitative Helly-type Hypergraph Chains”
  • Victor Milenkovic and Elisha Sacks. “Efficient Predicate Evaluation using Statistical Degeneracy Detection”
  • Therese Biedl. “Drawing complete outer-1-planar graphs in linear area”
  • Anna Lubiw and Graeme Stroud. “Computing Realistic Terrains from Imprecise Elevations”
  • Hwi Kim, Jaegun Lee and Hee-Kap Ahn. “Uniformly Monotone Partitioning of Polygons Revisited”
  • Ovidiu Daescu and Ka Yaw Teo. “Fast Deterministic Approximation of Medoid in Rd.
  • Ovidiu Daescu and Ka Yaw Teo. “The Median Line Segment Problem: Computational Complexity and Constrained Variants”
  • Giovanni Viglietta. “A Theory of Spherical Diagrams”
  • Prosenjit Bose, Guillermo Esteban and Anil Maheshwari. “Weighted shortest path in equilateral triangular meshes”
  • Stephane Durocher, Alexandre Leblanc and Sachini Rajapakse. “Computing Batched Depth Queries and the Depth of a Set of Points”
  • Gill Barequet, Shion Fukuzawa, Michael Goodrich, David Mount, Martha Osegueda and Evrim Ozel. “Diamonds are Forever in the Blockchain: Geometric Polyhedral Point-Set Pattern Matching”
  • David Eppstein. “Reflections in an Octagonal Mirror Maze”
  • David Eppstein. “Locked and Unlocked Smooth Embeddings of Surfaces”
  • David Eppstein. “Orthogonal Dissection into Few Rectangles”
  • Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon and Hee-Kap Ahn. “Approximating Convex Polygons by Histogons”
  • Ahmad Biniaz, Prosenjit Bose and Patrick Devaney. “A 13/9-approximation of the average-2π/3-MST”
  • Joseph O'Rourke, Anna Lubiw, Ryuhei Uehara, Chie Nara, Thomas Hull, Klara Mundilova and Josef Tkadlec. “Quasi-Twisting Convex Polyhedra”
  • Erik D. Demaine, Hiro Ito, Jayson Lynch and Ryuhei Uehara. “Computational Complexity of Flattening Fixed-Angle Orthogonal Chains”
  • Josef Minařík. “Unfolding Some Classes of One-Layer Polycubes” 
  • Stephane Durocher and Spencer Szabados. “Curve Stabbing Depth: Data Depth for Plane Curves”
  • Mark Keil, Debajyoti Mondal and Ehsan Moradi. “Burning Number for the Points in the Plane” 
  • Dániel Garamvölgyi and Tibor Jordan. “Globally linked pairs in braced maximal outerplanar graphs”
  • Anna Schenfisch, Brittany Terese Fasy, Samuel Micka, David L. Millman and Lucia Williams. “Efficient Graph Reconstruction and Representation Using Augmented Persistence Diagrams”
  • Ali Mohammad Lavasani, Denis Pankratov and Mohammad Ali Abam. “Maximum Weight Convex Polytope”
  • Aditya Acharya and David Mount. “Optimally Tracking Labels on an Evolving Tree”
  • Aya Bernstine and Yehonatan Mizrahi. “Efficiently Enumerating Scaled Copies of Point Set Patterns”
  • Neeldhara Misra, Harshil M. and Saraswati Nanoti. “Diverse Non Crossing Matchings”
  • Mohammad Javad Eslami-Bidgoli and Hamid Zarrabi-Zadeh. “Minimum Enclosing Spherical/Cylindrical Shells in High-Dimensional Streams”
  • Alireza Shavali and Hamid Zarrabi-Zadeh. “On the Biplanar and k-Planar Crossing Numbers”
  • Amirhossein Mozafari, Binay Bhattacharya and Tsunehiko Kameda. “A Sub-quadratic Algorithm for the Proximity Connected k-center Problem on Paths via Modular Arithmetic”
  • Kirby Gordon, Jacob Lezberg and Aaron Williams. “Unstacking Slabs in Megalit is NP-Hard”
  • Shahin Kamali and Pooya Nikbakht. “Online Square Packing with Rotation”
  • Robert Barish and Tetsuo Shibuya. “Optimally Confining Lattice Polymers”
  • Shahin Kamali, Pooya Nikbakht and Arezoo Sajadpour. “A Randomized Algorithm for Non-crossing Matching of Online Points”
Canadian Conference of Computational Geometry 2022 logo