April 20, 2014
23rd Canadian Conference on Computational Geometry
August 10-12, 2011

Hosted by the Fields Institute, held at Bahen Building, BA 1160
Univ. of Toronto map

Organizing Committee
Greg Aloupis, Academia Sinica and David Bremnerw

Conference home page Registration: Fee $150 before July 15, $200 after July 15
online to Aug. 3, on site Aug.10
Proceedings 2011 Accommodation Resources
Participant List Schedule On campus residences

The Canadian Conference on Computational Geometry is an annual international event for the dissemination of new results in the fields of computational and combinatorial geometry. The 23rd Canadian Conference on Computational Geometry (CCCG'11) will be held in Toronto, August 10-12, 2011 (reception on 9th).

Important Deadlines

Submission: May, 2011
Notification: About 3-4 weeks later
Final version: 1 week after that
Registration: A week or two after revision

Draft Schedule

August 9 Tuesday
Reception Knox College ~5pm, until 7:30 (ish)

August 10 Wednesday

BA 1170
BA 1200
Opening remarks
Previews (24) Previews are for sessions 1-2
William Steiger, Rutgers University
Geometric Partitioning
Coffee Break
BA 1170
BA 1200

Session 1

56 Convex blocking and partial orders on the plane
Canek Peláez, José Miguel Díaz-Báñez, Marco A. Heredia, J. Antoni Sellarès, Jorge Urrutia and Inmaculada Ventura.

22 On k-Gons and k-Holes in Point Sets
Birgit Vogtenhuber, Oswin Aichholzer, Ruy Fabila-Monroy, Clemens Huemer, Jorge Urrutia, Marco A. Heredia, Hernan Gonzalez-Aguilar, Thomas Hackl and Pavel Valtr.

99 Hardness Results for Two-Dimensional Curvature-Constrained Motion Planning
David Kirkpatrick, Irina Kostitsyna and Valentin Polishchuk.

Session 1

54 Optimizing Budget Allocation in Graphs
Boaz Benmoshe, Eran Omri and Michael Elkin.

8 Bottleneck Steiner Tree with Bounded Number of Steiner Vertices
A. Karim Abu-Affash, Paz Carmi and Matthew Katz.

35 Connecting Two Trees with Optimal Routing Cost
Mong-Jen Kao, Bastian Katz, Marcus Krug, Der-Tsai Lee, Martin Nöllenburg, Ignaz Rutter and Dorothea Wagner.

Session 1

29 Minimum Many to Many Matchings for Computing the Distance Between Two Sequences
David Rappaport, Godfried Toussaint and Mustafa Mohamad.

97 Staying Close to a Curve
Anil Maheshwari, Jörg-Rüdiger Sack, Kaveh Shahbaz and Hamid Zarrabi-Zadeh.

88 Isotopic Frechet Distance
Erin Chambers, David Letscher, Tao Ju and Lu Liu.
BA 1170
BA 1200

Session 2

107 Edge Unfoldings of Platonic Solids Never Overlap
Takashi Horiyama and Wataru Shoji.

38 Development of Curves on Polyhedra via Conical Existence
Joseph O'Rourke and Costin Vilcu.

49 Common Developments of Several Different Orthogonal Boxes
Zachary Abel, Erik Demaine, Martin Demaine, Hiroaki Matsui, Guenter Rote and Ryuhei Uehara.

43 Edge-Unfolding Orthogonal Polyhedra is Strongly NP-Complete
Zachary Abel and Erik D. Demaine.

85 A Topologically Convex Vertex-Ununfoldable Polyhedron
Zachary Abel, Erik D. Demaine and Martin L. Demaine.

Session 2

89 Isoperimetric Triangular Enclosure with a Fixed Angle
Prosenjit Bose and Jean-Lou De Carufel.

1 Robust approximate assembly partitioning
Elisha Sacks, Victor Milenkovic and Yujun Wu.

75 Approximation Algorithms for a Triangle Enclosure Problem
Karim Douieb, Matthew Eastman, Anil Maheshwari and Michiel Smid.

3 Finding the Maximum Area Parallelogram in a Convex Polygon
Kai Jin and Kevin Matulef.

32 Illumination problems on translation surfaces with planar infinities
Nikolay Dimitrov.


Session 2

16 Detecting VLSI Layout and Connectivity Errors in a Query Window
Ananda Swarup Das, Prosenjit Gupta and Kannan Srinathan.

17 Finding Maximum Density Axes Parallel Regions for Weighted Point Sets
Ananda Swarup Das, Prosenjit Gupta, Kannan Srinathan and Kishore Kothapalli.

83 Bichromatic Line Segment Intersection Counting in O(n sqrt(log n)) Time
Timothy M. Chan and Bryan T. Wilkinson.

27 Sequential Dependency Computation via Geometric Data Structures
Gruia Calinescu and Howard Karloff.

78 Point Location in Well-Shaped Meshes Using Jump-and-Walk
Jean-Lou De Carufel, Craig Dillabaugh and Anil Maheshwari.

Coffee Break
Open problems

Previews for sessions 3-4
Reception Wednesday at Panorama lounge, 6pm-8pm

August 11 Thursday

BA 1170
BA 1200
BA 1210

Session 3

91 Where and How Chew's Second Delaunay Refinement Algorithm Works
Alexander Rand.

42 Probabilistic Bounds on the Length of a Longest Edge in Delaunay Graphs of Random Points in d-Dimensions
Esther M. Arkin, Antonio Fernandez Anta, Joseph S. B. Mitchell and Miguel A. Mosteiro.

59 Outerplanar graphs and Delaunay triangulations
Md. Ashraful Alam, Igor Rivin and Ileana Streinu.

57 Toward the Tight Bound of the Stretch Factor of Delaunay Triangulations
Ge Xia and Liang Zhang.

Session 3

52 Rigid components in fixed-lattice and cone frameworks
Matthew Berardi, Brent Heeringa, Justin Malestein and Louis Theran.

74 Orientations of Simplices Determined by Orderings on the Coordinates of their Vertices
Emeric Gioan, Kevin Sol and Gérard Subsol.

44 Pushing the boundaries of polytopal realizability
David Bremner,
Antoine Deza, William Hua and Lars Schewe.

47 On the generation of topological $(n_k)$-configurations
Jürgen Bokowski and Vincent Pilaud.

Session 3

62 Sliding labels for dynamic point labeling
Andreas Gemsa, Martin Nöllenburg and Ignaz Rutter.

28 A Discrete and Dynamic Version of Klee’s Measure Problem
Hakan Yýldýz, John Hershberger and Subhash Suri.

9 Kinetically-aware Conformational Distances in Molecular Dynamics
Chen Gu, Xiaoye Jiang and Leonidas Guibas.

55 Collinearities in Kinetic Point Sets
Benjamin Lund, George Purdy, Justin Smith and Csaba Toth.

Coffee Break

Session 4

70 Convexifying Polygons Without Losing Visibilities
Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Vida Dujmoviæ, Ferran Hurtado, Anna Lubiw, Günter Rote, André Schulz, Diane L. Souvaine and Andrew Winslow.

96 Expansive Motions for d-Dimensional Open Chains
Sarah Eisenstat and Erik D. Demaine.

34 Making triangulations 4-connected using flips
Prosenjit Bose, Dana Jansens, André Van Renssen, Maria Saumell and Sander Verdonschot.

Session 4

53 Approximating the Medial Axis by Shooting Rays: 3D Case
Svetlana Stolpner, Kaleem Siddiqi and Sue Whitesides.

30 An Incremental Algorithm for High Order Maximum Voronoi Diagram Construction
Khuong Vu and Rong Zheng.

12 Approximating a Motorcycle Graph by a Straight Skeleton
Stefan Huber and Martin Held.

Session 4

11 Small Octahedral Systems
Grant Custard, Antoine Deza, Tamon Stephen and Feng Xie.

68 Combinatorics of Minkowski decomposition of associahedra
Carsten Lange.

10 A Fourier-Theoretic Approach for Inferring Symmetries
Xiaoye Jiang, Jian Sun and Leonidas Guibas.

BA 1170
BA 1200
(room available1:00 -5pm)
BA 1210

Noga Alon, Tel Aviv University
List coloring and Euclidean Ramsey Theory
Business Meeting
Coffee Break
Previews for sessions 5-6.

Session 5

20 Rigidity-Theoretic Constructions of Integral Fary Embeddings
Timothy Sun.

36 Drawing some planar graphs with integer edge-lengths
Therese Biedl.

101 Approximating the Obstacle Number for a Graph Drawing Efficiently
Deniz Sarioz.

25 A Note on Minimum-Segment Drawings of Planar Graphs
Stephane Durocher, Debajyoti Mondal, Rahnuma Islam Nishat and Sue Whitesides.

Session 5

40 Characterization of Shortest Paths on Directional Frictional Polyhedral Surfaces
Gutemberg Guerra Filho and Pedro J. De Rezende.

15 Memory-Constrained Algorithms for Shortest Path Problem
Tetsuo Asano and Benjamin Doerr.

82 Finding Optimal Geodesic Bridges Between Two Simple Polygons
Amit Bhosle and Teofilo Gonzalez.

81 Approximating Geodesic Distances on 2-Manifolds in R^3
Christian Scheffer and Jan Vahrenhold.

Session 5

41 An In-Place Priority Search Tree
Minati De, Anil Maheshwari, Subhas Nandy and Michiel Smid.

106 Orthogonal Range Search using a Distributed Computing Model
Pouya Bisadi and Bradford Nickerson.

61 On Finding Skyline Points for Range Queries in Plane
Anil Kishore Kalavagattu, Ananda Swarup Das, Kishore Kothapalli and Kannan Srinathan.

37 Space-efficient Algorithms for Empty Space Recognition among a Point Set in 2D and 3D
Minati De and Subhas Nandy.

Reception: Thursday at Hart House, 6pm-8pm.

August 12 Friday

BA 1170
BA 1200
(room available 9 am-5:00 pm)

Session 6

23 Realizing Site Permutations
Stephane Durocher, Saeed Mehrabi, Debajyoti Mondal and Matthew Skala.

86 Establishing Strong Connectivity using Optimal Radius Half-Disk Antennas
Greg Aloupis, Mirela Damian, Robin Flatland, Matias Korman, Ozgur Ozkan, David Rappaport and Stefanie Wuhrer.

92 Euclidean Movement Minimization
Mohammadamin Fazli, Mohammadali Safari, Nima Anari, Pooya Jalaly Khalilabadi and Mohammad Ghodsi.

2 A Randomly Embedded Random Graph is Not a Spanner
Abbas Mehrabian.

Session 6

31 Approximation Algorithms for the Discrete Piercing Set Problem for Unit Disks
Minati De, Gautam Das and Subhas Nandy.

24 New Lower Bounds for the Three-dimensional Orthogonal Bin Packing Problem
Chia-Hong Hsu and Chung-Shou Liao.

14 The 2×2 Simple Packing Problem
André Van Renssen and Bettina Speckmann.

5 On covering of any point configuration by disjoint unit disks
Yosuke Okayama, Masashi Kiyomi and Ryuhei Uehara.

Session 6

46 Improving Accuracy of GNSS Devices in Urban Canyons
Boaz Ben-Moshe, Elazar Elkin, Harel Levi and Ayal Weissman.

84 Geometry-Free Polygon Splitting
Sherif Ghali.

6 Robustness of topology of digital images and point clouds
Peter Saveliev.

4 Planar Pixelations and Shape Reconstruction
Brandon Rowekamp.

Coffee Break
Previews for Session 7
Emo Welzl, ETH Zurich
Counting Simple Polygonizations of Planar Point Sets
BA 1170
BA 1200



Session 7

69 Algorithms for Bivariate Majority Depth
Dan Chen and Pat Morin.

102 Exact Algorithms and APX-Hardness Results for Geometric Set Cover
Elyot Grant and Timothy Chan.

65 Enumerating Minimal Transversals of Geometric Hypergraphs
Khaled Elbassioni, Imran Rauf and Saurabh Ray.

104 Helly Numbers of Polyominoes
Jean Cardinal, Hiro Ito, Matias Korman and Stefan Langerman.

Session 7

58 Open Guard Edges and Edge Guards in Simple Polygons
Csaba Toth, Godfried Toussaint and Andrew Winslow.

63 Computing k-Link Visibility Polygons in Environments with a Reflective Edge
Salma Sadat Mahdavi, Ali Mohades and Bahram Kouhestani.

50 Edge-guarding Orthogonal Polyhedra
Giovanni Viglietta, Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Anastasia Kurdia, Joseph O'Rourke, Godfried Toussaint and Jorge Urrutia.

18 Wireless Localization within Orthogonal Polyhedra
Tobias Christ and Michael Hoffmann.

95 Weak Visibility Queries in Simple Polygons
Mojtaba Nouri Bygi and Mohammad Ghodsi.

Session 7

21 The Possible Hull of Imprecise Points
Jeff Sember and William Evans.

87 A Slow Algorithm for Computing the Gabriel Graph with Double Precision
David L. Millman and Vishal Verma.

77 An Experimental Analysis of Floating-Point Versus Exact Arithmetic
Martin Held and Willi Mann.

72 On Inducing n-gons
Marjan Abedin, Ali Mohades and Marzieh Eskandari.

48 Weak Matching Points with Triangles
Fatemeh Panahi, Ali Mohades, Mansoor Davoodi and Marzieh Eskandari.

List of Confirmed Participants as of July 31, 2011:

Full Name University/Affiliation
Abel, Zachary Massachusetts Institute of Technology
Abu-Affash, A.Karim Ben-Gurion University
Aichholzer, Oswin Technische Universität Graz
Alam, Md. Ashraful University of Massachusetts
Alamdari, Soroush University of Waterloo
Alon, Noga Tel Aviv University
Aloupis, Greg ULB
Asano, Tetsuo JAIST
Bae, Wan University of Wisconsin-Stout
Basit, Abdul Rutgers, The State University of New Jersey
Beingessner, Alexis Carleton University
Benmoshe, Boaz Ariel University Center
Berardi, Matthew Temple University
Biedl, Therese University of Waterloo
Bint, Gregory Carleton University
Bisadi, Pouya University of New Brunswick
Bitner, Steven US Army TRADOC Analysis Center
Bose, Prosenjit Carleton University
Bremner, David University of New Brunswick
Calinescu, Gruia Illinois Institute of Technology
Cannon, Sarah Tufts University
Cardinal, Jean Université Libre de Bruxelles
Chen, Dan Carleton University
Cheng, Howard University of Arizona
Christ, Tobias ETH Zürich
Claude, Francisco University of Waterloo
Collette, Sébastien Universite Libre de Bruxelles
Damian, Mirela Villanova University
Das, Ananda Swarup IIIT Hyderabad
De Carufel, Jean-Lou Carleton University
De, Minati Carleton University and Indian Statistical Institute
Debnath, Narayan Winona State University
Demaine, Erik Massachusetts Institute of Technology
Demaine, Martin Massachusetts Institute of Technology
Devadoss, Satyan Williams College
Deza, Antoine McMaster University
Dillabaugh, Craig Carleton University
Dimitrov, Nikolay McGill University
Dorrigiv, Reza University of Waterloo
Durocher, Stephane University of Manitoba
Eastman, Matthew Carleton University
Eisenstat, Sarah Massachusetts Institute of Technology
Eskandari, Marzieh Alzahra University
Flatland, Robin Siena College
Fraser, Bob University of Waterloo
Ge, Xia Lafayette College
Gemsa, Andreas Karlsruhe Institute of Technology
Ghali, Sherif  
Gheibi, Amin Carleton University
Grant, Elyot University of Waterloo
Grimm, Carsten Carleton University
Gu, Chen Stanford University
Guerra-Filho, Gutemberg University of Texas at Arlington
Hartmann, Tanja Karlsruhe Institute of Technology
He, Meng University of Waterloo
Heeringa, Brent Williams College
Hoda, Nima Carleton University
Hoffmann, Michael ETH Zürich
Horiyama, Takashi Saitama University
Howat, John Carleton University
Hsu, Chia-Hong National Tsing Hua University
Huber, Stefan Universität Salzburg
Iacono, John Polytechnic Institute of New York University
Jansens, Dana Carleton University
Jiang, Xiaoye Stanford University
Jin, Kai IIIS, Tsinghua University
Kamali, Shahin University of Waterloo
Kao, Mong-Jen National Taiwan University
Kao, Pei-Hsun National Taiwan University
Kirkpatrick, David University of British Columbia
Kiyomi, Masashi Japan Advanced Institute of Science and Technology
Korman, Matias ULB
Kurdia, Anastasia Connecticut College
Lai, Po Kong Carleton University
Lange, Carsten Freie Universität Berlin
Langerman, Stefan Université Libre de Bruxelles
Larionov, Egor University of Waterloo
Letscher, David Saint Louis University
Li, Brian Williams College
Li, Simon Douglas College
Liao, Chung-Shou National Tsing Hua Unviersity
Löffler, Maarten University of California, Irvine
Lubiw, Anna University of Waterloo
Lund, Benjamin University of Cincinnati
Mehrabi, Saeed University of Manitoba
Mehrabian, Abbas University of Waterloo
Milenkovic, Victor University of Miami
Millman, David UNC-Chapel Hill
Mohades, Ali Amirkabir University of Technology
Mohamad, Mustafa Queen's University
Mondal, Debajyoti University of Manitoba
Morin, Patrick Carleton University
Morrison, Jason University of Manitoba
Mosteiro, Miguel A. Rutgers University
Nicholson, Patrick University of Waterloo
Nickerson, Brad University of New Brunswick
Nishat, Rahnuma Islam University of Victoria
Nollenburg, Martin Karlsruhe Institute of Technology
Nouri Bygi, Mojtaba Sharif University of Technology
O'Rourke, Joseph Smith College
Owen, Megan Fields Institute
Pathak, Vinayak University of Waterloo
Peláez Valdés, Canek Universidad Nacional Autónoma de México
Pilaud, Vincent Fields Institute and Université Paris 7
Pratt, Simon Carleton University
Rand, Alexander The University of Texas at Austin
Rappaport, David Queen's University
Ray, Saurabh Max Plank Institute for Informatics
Risteski, Andrej Princeton University
Rowekamp, Brandon University of Notre Dame
Sacks, Elisha Purdue University
Saeedi, Noushin University of British Columbia
Safari, Mohammad Ali Sharif University of Technology
Salinger, Alejandro University of Waterloo
Sarioz, Deniz CUNY Graduate Center
Saveliev, Peter Marshall University
Scheffer, Christian TU Dortmund
Schumm, Andrea Karlsruhe Institute of Technology
Sember, Jeff University of British Columbia
Shahbaz, Kaveh Carleton University
Skala, Matthew University of Manitoba
Smid, Michiel Carleton University
Sol, Kevin LIRMM, University of Montpellier 2
Souvaine, Diane Tufts University
Steiger, William Rutgers University
Stolpner, Svetlana Queen's University
Sun, Timothy Columbia University
Taslakian, Perouz Universite Libre de Bruxelles
Theran, Louis Temple University
Thomas, Hugh University of New Brunswick
Uehara, Ryuhei Japan Advanced Institute of Science and Technology
Urrutia, Jorge Universidad Nacional Autónoma de México
Vahrenhold, Jan Technische Universität Dortmund
van Renssen, André Carleton University
Vatshelle, Martin University of Bergen
Verdonschot, Sander Carleton University
Viglietta, Giovanni University of Pisa
Vogtenhuber, Birgit Technische Universität Graz
Vu, Khuong University of Houston
Welzl, Emo ETH Zurich
Wilkinson, Bryan T. University of Waterloo
Winslow, Andrew Tufts University
Yildiz, Hakan University of California, Santa Barbara
Zangooei, Somayyeh University of Waterloo


Back to top