Computational Topology in Reconstruction, Mesh Generation, and Data Analysis Tamal K. Dey, pp. 1 [Download PDF]
Session 1A - Monday Aug. 11, 10:00-10:50
Kinetic Data Structures for the Semi-Yao Graph and All Nearest Neighbors in R^d Zahed Rahmati, Mohammad Ali Abam, Valerie King and Sue Whitesides, pp. 2-10 [Download PDF]
Windows into Geometric Events: Data Structures for Time-Windowed Querying of Temporal Point Sets Michael J. Bannister, William E. Devanny, Michael T. Goodrich, Joseph A. Simons and Lowell Trott, pp. 11-19 [Download PDF]
Session 1B - Monday Aug. 11, 10:00-10:50
Computing the Geodesic Centers of a Polygonal Domain Sang Won Bae, Matias Korman and Yoshio Okamoto, pp. 20-25 [Download PDF]
Space-Efficient Algorithm for Computing a Centerpoint of a Point Set in R^2 Binay K. Bhattacharya, Subhas C. Nandy and Sasanka Roy, pp. 26-32 [Download PDF]
Session 2A - Monday Aug. 11, 11:15-12:30
Quality Ratios of Measures for Graph Drawing Styles Michael Hoffmann, Marc van Kreveld, Vincent Kusters and Günter Rote, pp. 33-39 [Download PDF]
Drawing Plane Triangulations with Few Segments, pp. 40-45 Stephane Durocher and Debajyoti Mondal [Download PDF]
Non-Shellable Drawings of Kn with Few Crossings Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Pedro Ramos and Birgit Vogtenhuber, pp. 46-51 [Download PDF]
Session 2B - Monday Aug. 11, 11:15-12:30
On the Computational Complexity of Partitioning Weighted Points into a Grid of Quadrilaterals Alexander Idelberger and Maciej Liskiewicz, pp. 52-60 [Download PDF]
Minimum Dilation Triangulation: Reaching Optimality Efficiently Aléx F. Brandt, Miguel M. Gaiowski, Cid C. de Souza and Pedro J. de Rezende, pp. 61-66 [Download PDF]
An Improved Method for Generating Triangle-Mesh Models of Images Xiao (Brian) Ma and Michael D. Adams, pp. 67-72 [Download PDF]
Session 3A - Monday Aug. 11, 14:00-15:40
On the Chromatic Art Gallery Problem Sándor P. Fekete, Stephan Friedrichs, Michael Hemmer, Joseph B. M. Mitchell and Christiane Schmidt, pp. 73-79 [Download PDF]
Covering Orthogonal Polygons with Sliding k-Transmitters Salma Sadat Mahdavi, Saeed Seddighin and Mohammad Ghodsi, pp. 80-84 [Download PDF]
On the VC-Dimension of Visibility in Monotone Polygons Matt Gibson, Erik Krohn and Qing Wang, pp. 85-94 [Download PDF]
Representing a Planar Straight-Line Graph Using Few Obstacles Matthew P. Johnson and Deniz Sariöz, pp. 95-99 [Download PDF]
Session 3B - Monday Aug. 11, 14:00-15:40
Continuous Yao Graphs Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, Mirela Damian, Rolf Fagerberg, André van Renssen, Perouz Taslakian and Sander Verdonschot, pp. 100-106 [Download PDF]
A Note on Online Steiner Tree Problems Gokarna Sharma and Costas Busch, pp. 107-112 [Download PDF]
Approximating Full Steiner Tree in a Unit Disk Graph Ahmad Biniaz, Anil Maheshwari and Michiel Smid, pp. 113-117 [Download PDF]
A Linear Time Euclidean Spanner on Imprecise Points Jiemin Zeng and Jie Gao, pp. 118-124 [Download PDF]
Session 4A - Monday Aug. 11, 16:05-17:45
The Duality of Geodesic Voronoi/Delaunay Diagrams For An Intrinsic Discrete Laplace-Beltrami Operator on Simplicial Surfaces Yong-Jin Liu, Chunxu Xu, Ying He and Deok-Soo Kim, pp. 125-132 [Download PDF]
Forest-Like Abstract Voronoi Diagrams in Linear Time Cecilia Bohler, Rolf Klein and Chih-Hung Liu, pp. 133-141 [Download PDF]
Voronoi Games and Epsilon Nets Aritra Banik, Jean-Lou De Carufel, Anil Maheshwari and Michiel Smid, pp. 142-147 [Download PDF]
Straight Skeletons by Means of Voronoi Diagrams Under Polyhedral Distance Functions Stefan Huber, Oswin Aichholzer, Thomas Hackl and Birgit Vogtenhuber, pp. 148-154 [Download PDF]
Session 4B - Monday Aug. 11, 16:05-17:45
Sphere Packing with Limited Overlap Mabel Iglesias-Ham, Michael Kerber and Caroline Uhler, pp. 155-161 [Download PDF]
Almost Online Square Packing Shahin Kamali and Alejandro López-Ortiz, pp. 162-168 [Download PDF]
Minimum Convex Container of Two Convex Polytopes under Translations Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Dongwoo Park and Chan-Su Shin, pp. 169-174 [Download PDF]
Uniqueness of Optimal Cube Wrapping Qinxuan Pan, pp. 175-183 [Download PDF]
Plenary talk - Tuesday Aug. 11, 9:00-10:00
Cuttings in 2D Revisited Timothy M. Chan, pp. 184 [Download PDF]
Session 5A - Tuesday Aug. 12, 10:00-10:50
Graph Drawings with Relative Edge Length Specifications Oswin Aichholzer, Michael Hoffmann, Marc Van Kreveld and Günter Rote, pp. 185-191 [Download PDF]
Drawing the Horton Set in an Integer Grid of Minimun Size Luis Barba, Frank Duque, Ruy Fabila-Monroy and Carlos Hidalgo-Toscano, pp. 192-197 [Download PDF]
Session 5B - Tuesday Aug. 12, 10:00-10:50
On Combinatorial Depth Measures Stephane Durocher, Robert Fraser, Alexandre Leblanc, Jason Morrison and Matthew Skala, pp. 198-205 [Download PDF]
Decontaminating Planar Regions by Sweeping with Barrier Curves Borislav Karaivanov, Minko Markov, Jack Snoeyink and Tzvetalin S. Vassilev, pp. 206-211 [Download PDF]
Session 6A - Tuesday Aug. 12, 11:15-12:30
Low Space Data Structures for Geometric Range Mode Query Stephane Durocher, Hicham El-Zein, J. Ian Munro and Sharma V. Thankachan, pp. 212-215 [Download PDF]
A Succinct, Dynamic Data Structure for Proximity Queries on Point Sets Prayaag Venkat and David M. Mount, pp. 216-225 [Download PDF]
Maximum Independent Set for Interval Graphs and Trees in Space Efficient Models Binay K. Bhattacharya, Minati De, Subhas C. Nandy and Sasanka Roy, pp. 226-232 [Download PDF]
Session 6B - Tuesday Aug. 12, 11:15-12:30
Packing Plane Spanning Trees and Paths in Complete Geometric Graphs Oswin Aichholzer, Thomas Hackl, Matias Korman, Marc Van Kreveld, Maarten Löffler, Alexander Pilz, Bettina Speckmann and Emo Welzl, pp. 233-238 [Download PDF]
On the Spanning Ratio of Constrained Yao-Graphs André van Renssen, pp. 239-243 [Download PDF]
The Convex Hull of Points on a Sphere is a Spanner Prosenjit Bose, Simon Pratt and Michiel Smid, pp. 244-250 [Download PDF]
Session 7A - Tuesday Aug. 12, 16:00-14:50
Turning Orthogonally Convex Polyhedra into Orthoballs Fidel Barrera-Cruz, Therese Biedl, Martin Derka, Stephen Kiazyk, Anna Lubiw and Hamideh Vosoughpour, pp. 251-257 [Download PDF]
Bumpy Pyramid Folding Zachary R. Abel, Erik D. Demaine, Martin L. Demaine, Hiro Ito, Jack Snoeyink and Ryuhei Uehara, pp. 258-266 [Download PDF]
Session 7B - Tuesday Aug. 12, 16:00-14:50
Order types and cross-sections of line arrangements in R^3 Oswin Aichholzer, Ruy Fabila-Monroy, Ferran Hurtado, Pablo Pérez-Lantero, Andres J. Ruiz-Vargas, Jorge Urrutia and Birgit Vogtenhuber, pp. 267-272 [Download PDF]
Dimension Detection with Local Homology Tamal K. Dey, Fengtao Fan and Yusu Wang, pp. 273-279 [Download PDF]
Plenary talk - Wednesday Aug. 13, 9:00-10:00
Time, Space, and Precision: Revisiting Classic Problems in Computational Geometry with Degree-Driven Analysis, pp. 280 Jack Snoeyink [Download PDF]
Session 8A - Wednesday Aug. 13, 10:00-10:50
Window Queries On Planar Subdivisions Arising From Overlapping Polygons Stuart A. Macgillivray and Bradford C. Nickerson, pp. 281-286 [Download PDF]
Improved Bounds for Smallest Enclosing Disk Range Queries Sankalp Khare, Jatin Agarwal, Nadeem Moidu and Kannan Srinathan, pp. 287-291 [Download PDF]
Session 8B - Wednesday Aug. 13, 10:00-10:50
On the d-Runaway Rectangle Escape Problem Aniket Basu Roy, Sathish Govindarajan, Neeldhara Misra and Shreyas Shetty, pp. 292-301 [Download PDF]
The Maximum Disjoint Set of Boundary Rectangles Amirmahdi Ahmadinejad and Hamid Zarrabi-Zadeh, pp. 302-307 [Download PDF]
Session 9A - Wednesday Aug. 13, 11:15-12:30
Covering Grids by Trees Adrian Dumitrescu and Csaba Tóth, pp. 308-313 [Download PDF]
Geometric Hitting Set and Set Cover Problem with Half-Strips Apurva Mudgal and Supantha Pandit, pp. 314-318 [Download PDF]
A Distributed Algorithm for Approximate Mobile Sensor Coverage Esther Ezra, Jiemin Zeng and Jie Gao, pp. 319-325 [Download PDF]
Session 9B - Wednesday Aug. 13, 11:15-12:30
The τ-Skyline for Uncertain Data Haitao Wang and Wuzhou Zhang, pp. 326-331 [Download PDF]
Pursuit and Evasion with Uncertain Bearing Measurements Josh Vander Hook and Volkan Isler, pp. 332-340 [Download PDF]
The Generalized Minimum Manhattan Network Problem (GMMN) - Scale Diversity Aware Approximation and a Primal-Dual Algorithm Stefan Funke and Martin P. Seybold, pp. 341-347 [Download PDF]
Session 10A - Wednesday Aug. 13, 14:00-15:40
The Mutual Visibility Problem for Oblivious Robots Giuseppe Antonio Di Luna, Paola Flocchini, Federico Poloni, Nicola Santoro and Giovanni Viglietta, pp. 348-354 [Download PDF]
Visibility Graphs, Dismantlability, and the Cops and Robbers Game Anna Lubiw, Jack Snoeyink and Hamideh Vosoughpour, pp. 355-366 [Download PDF]
A PTAS for the Continuous 1.5D Terrain Guarding Problem Stephan Friedrichs, Michael Hemmer and Christiane Schmidt, pp. 367-373 [Download PDF]
Routing in a Polygonal Terrain with the Shortest Beacon Watchtower Bahram Kouhestani, David Rappaport and Kai Salomma, pp. 374-379 [Download PDF]
Session 10B - Wednesday Aug. 13, 14:00-15:40
A Separator Theorem for Intersecting Objects in the Plane Nabil Mustafa, Rajiv Raman and Saurabh Ray, pp. 380-385 [Download PDF]
The Convex Configurations of "Sei Shonagon Chie no Ita" and Other Dissection Puzzles Eli Fox-Epstein and Ryuhei Uehara, pp. 386-389 [Download PDF]
Searching by Panning and Zooming Prosenjit Bose, John Howat and Pat Morin, pp. 390-394 [Download PDF]
Quickly Placing a Point to Maximize Angles Boris Aronov and Mark Yagnatinsky, pp. 395-400 [Download PDF]
Session 11A - Wednesday Aug. 13, 16:05-17:45
Colored Ray Configurations Ruy Fabila-Monroy, Alfredo García, Ferran Hurtado, Rafel Jaume, Pablo Pérez-Lantero, Maria Saumell, Rodrigo I. Silveira, Javier Tejel and Jorge Urrutia, pp. 401-406 [Download PDF]
Planar Graphs with Many Perfect Matchings and Forests Michael Biro, pp. 407-411 [Download PDF]
On the Use of Adaptive, Exact Decisions Number Types Based on Expression-Dags in Geometric Computing Stefan Schirra, pp. 412-418 [Download PDF]
An Incidence Geometry Approach to Dictionary Learning Meera Sitharam, Mohamad Tarifi and Menghan Wang, pp. 419-430 [Download PDF]
Session 11B - Wednesday Aug. 13, 16:05-17:20
Bottleneck Bichromatic Plane Matching of Points Ahmad Biniaz, Anil Maheshwari and Michiel Smid, pp. 431-435 [Download PDF]
All Approximating Segments for a Sequence of Points Ghobad Emadi and Alireza Zarei, pp. 436-442 [Download PDF]
Approximate Matching of Curves to Point Sets Paul Accisano and Alper Üngör, pp. 443-450 [Download PDF]