 |
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
Brunswick
|
OVERVIEW
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
|
BA1160
|
BA1210
|
|
9:00-9:10
|
x
|
x
|
Opening
remarks
|
x
|
|
9:10-9:40
|
x
|
x
|
Previews
(24) Previews are for sessions 1-2
|
x
|
|
9:40-10:40
|
x
|
x
|
William
Steiger, Rutgers University
Geometric Partitioning
|
x
|
|
10:40-11:00
|
Coffee
Break
|
|
Room
|
BA
1170
|
BA
1200
|
BA1160
|
BA1210
|
|
11:00-12:00
|
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.
|
x
|
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. |
|
12:00-13:30
|
Lunch
|
|
Room
|
BA
1170
|
BA
1200
|
BA1160
|
BA1210
|
|
13:30-15:10
|
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.
|
x
|
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.
|
|
15:10-15:30
|
Coffee
Break
|
|
15:30-16:30
|
x
|
|
Open
problems
Previews for sessions 3-4
|
|
|
16:30-17:00
|
x
|
|
|
|
|
|
|
August
11 Thursday
|
|
Room
|
BA
1170
|
BA
1200
|
BA1160
|
BA
1210
|
|
9:00-10:20
|
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.
|
|
10:20-10:50
|
|
|
10:50-11:50
|
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.
|
|
11:50-13:30
|
Lunch
|
|
Room
|
BA
1170
|
BA
1200
|
BA1160
(room available1:00 -5pm)
|
BA
1210
|
|
13:30-14:30
|
|
x
|
Noga Alon, Tel Aviv University
List coloring and Euclidean Ramsey Theory
|
x
|
|
14:30-15:10
|
|
x
|
Business
Meeting
|
x
|
|
15:10-15:30
|
|
|
15:30-16:00
|
x
|
x
|
Previews
for sessions 5-6.
|
X
|
|
16:05-17:25
|
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
|
|
Room
|
BA
1170
|
BA
1200
|
BA1160
|
BA1210
(room available 9 am-5:00 pm)
|
|
9:00-10:20
|
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.
|
|
10:20-10:40
|
|
|
10:40-11:00
|
x
|
x
|
Previews
for Session 7
|
x
|
|
11:00-12:00
|
x
|
x
|
Emo
Welzl, ETH Zurich
Counting Simple Polygonizations of Planar Point Sets
|
x
|
|
12:00-13:30
|
Lunch
|
|
Room
|
BA
1170
|
BA
1200
|
BA1160
|
BA1210
|
|
13:30-15:10
|
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
|
|
