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 R^d, 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 R^d.
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”