Plenary talk - Monday Aug. 11, 9:00-10:00
- 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]