CCCG 2015 Proceedings
  • CCCG 2015 Complete Proceedings
    [Download PDF]

  • Paul Erdos Memorial Lecture
  • Connectivity Preserving Iterative Compression
    Bruce Reed, pp. 1
    [Download PDF]

  • Session 1A
  • An Algorithm for the Maximum Weight Independent Set Problem onOutersting Graphs
    Mark Keil, Joseph Mitchell, Dinabandhu Pradhan and Martin Vatshelle, pp. 2-7
    [Download PDF]
  • Duality for Geometric Set Cover and Geometric Hitting Set Problems on Pseudodisks
    Stephane Durocher and Robert Fraser, pp. 8-16
    [Download PDF]
  • Conflict-free Covering
    Esther Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew Katz, Joseph Mitchell and Marina Simakov, pp. 17-23
    [Download PDF]
  • Space Filling Curves for 3D Sensor Networks with Complex Topology
    Mayank Goswami, Siming Li, Junwei Zhang, Emil Saucan, David Xianfeng Gu and Jie Gao, pp. 23-30
    [Download PDF]

  • Session 1B
  • Inscribing H-Polyhedra in Quadrics Using a Projective Generalization of Closed Sets
    Willem Hagemann and Eike Moehlmann, pp. 31-36
    [Download PDF]
  • 1-string B1-VPG-representations of planar partial 3-trees and some subclasses
    Therese Biedl and Martin Derka, pp. 37-42
    [Download PDF]
  • Diversity Maximization via Composable Coresets
    Sepideh Aghamolaei, Majid Farhadi and Hamid Zarrabi-Zadeh, pp. 38-48
    [Download PDF]
  • An Upper Bound on Trilaterating Simple Polygons
    Matthew Dippel and Ravi Sundaram, pp. 49-56
    [Download PDF]

  • Session 2A
  • Constrained Empty-Rectangle Delaunay Graphs
    Prosenjit Bose, Jean-Lou De Carufel and Andre van Renssen, pp. 57-62
    [Download PDF]
  • Flips in Edge-Labelled Pseudo-Triangulations
    Prosenjit Bose and Sander Verdonschot, pp. 63-69
    [Download PDF]
  • The Shadows of a Cycle Cannot All Be Paths
    Giovanni Viglietta, Prosenjit Bose, Jean-Lou De Carufel, Michael Dobbins and Heuna Kim, pp. 70-75
    [Download PDF]

  • Session 2B
  • A Fault Tolerant Data Structure for Peer-to-Peer Range Query Processing
    Zahra Mirikharaji and Bradford Nickerson, pp. 76-82
    [Download PDF]
  • Range Counting with Distinct Constraints
    Ian Munro, Yakov Nekrich and Sharma V. Thankachan, pp. 83-88
    [Download PDF]
  • Bottleneck Segment Matching
    Aritra Banik, Matthew Katz and Marina Simakov, pp. 89-93
    [Download PDF]

  • Session 3A
  • Reconfiguring a Chain of Cubes
    Laurie Heyer, Anna Lubiw, Debajyoti Mondal, Ulrike Stege and Sue Whitesides, pp. 94-100
    [Download PDF]
  • Folding Polyominoes into (Poly)Cubes
    Oswin Aichholzer, Michael Biro, Erik D. Demaine, Martin Demaine, David Eppstein, Sandor Fekete, Adam Hesterberg, Irina Kostitsyna and Chrisatiane Schmidt, pp. 101-106
    [Download PDF]
  • Touring a Sequence of Line Segments in Polygonal Domain Fences
    Amirhossein Mozafari and Alireza Zarei, pp. 107-115
    [Download PDF]

  • Session 3B
  • A Geometric Perspective on Sparse Filtrations
    Nicholas Cavanna, Mahmoodreza Jahanseir and Don Sheehy, pp. 116-121
    [Download PDF]
  • Online Packing of Equilateral Triangles
    Shahin Kamali, Alejandro Lopez Ortiz and Zahed Rahmati, pp. 122-127
    [Download PDF]
  • Relaxed Disk Packing
    Mabel Iglesias-Ham, Herbert Edelsbrunner and Vitaliy Kurlin, pp. 128-135
    [Download PDF]

  • Session 4A
  • Approximating the Minimum Closest Pair Distance and Nearest Neighbor Distances of Linearly Moving Points
    Timothy M. Chan and Zahed Rahmati, pp. 136-140
    [Download PDF]
  • Time-Windowed Closest Pair
    Timothy M. Chan and Simon Pratt, pp. 141-144
    [Download PDF]
  • An Output-Sensitive Algorithm for Computing Weighted α-Complexes
    Donald Sheehy, pp. 145-150
    [Download PDF]
  • Dynamic data structures for approximate Hausdorff distance in the word RAM
    Timothy Chan and Dimitrios Skrepetos, pp. 151-155
    [Download PDF]

  • Session 4B
  • Local Doubling Dimension of Point Sets
    Aruni Choudhary and Michael Kerber, pp. 156-164
    [Download PDF]
  • A Streaming Algorithm for 2-Center with Outliers in High Dimensions
    Raimi Rufai and Dana Richards, pp. 165-172
    [Download PDF]
  • A Streaming Algorithm for the Convex Hull
    Behnam Hatami and Hamid Zarrabi-Zadeh, pp. 173-178
    [Download PDF]
  • Approximation and Streaming Algorithms for Projective Clustering via Random Projections
    Michael Kerber and Sharath Raghvendra, pp. 179-185
    [Download PDF]

  • Invited Plenary Lecture
  • Fun with Restricted Delaunay Triangulations
    Jonathan Shewchuk, pp. 186
    [Download PDF]

  • Session 5A
  • Algorithms for Minimizing the Movements of Spreading Points in Linear Domains
    Shimin Li and Haitao Wang, pp. 187-192
    [Download PDF]
  • Maximizing the Minimum Angle with the Insertion of Steiner Vertices
    Shankar Sastry, pp. 193-198
    [Download PDF]
  • An Output-Sensitive Algorithm for Computing the s-Kernel
    Leonidas Palios, pp. 199-204
    [Download PDF]

  • Session 5B
  • On the Inverse Beacon Attraction Region of a Point
    Bahram Kouhestani, David Rappaport and Kai Salomaa, pp. 205-212
    [Download PDF]
  • A Combinatorial Bound for Beacon-based Routing in Orthogonal Polygons
    Thomas Shermer, pp. 213-219
    [Download PDF]
  • Guarding Orthogonal Terrains
    Stephane Durocher, Pak Ching Li and Saeed Mehrabi, pp. 220-227
    [Download PDF]

  • Open Problem Session
  • Open Problems from CCCG 2014
    Sue Whitesides, pp. 228-231
    [Download PDF]

  • Ferran Hurtado Memorial Lecture
  • One of Ferran Hurtado’s favorite topics - Flips
    Prosenjit Bose, pp. 232
    [Download PDF]

  • Session 6A
  • Weighted Minimum Backward Frechet Distance
    Amin Gheibi, Anil Maheshwari and Jorg Sack, pp. 233-240
    [Download PDF]
  • Squeeze-free Hamiltonian Paths in Grid Graphs
    Robin Flatland and Alexandru Damian, pp. 241-255
    [Download PDF]
  • Strongly Connected Spanning Subgraph for Almost Symmetric Networks
    A. Karim Abu-Affash, Paz Carmi and Anat Parush Tzur, pp. 256-261
    [Download PDF]
  • A Faster 4-Approximation Algorithm for the Unit Disk Cover Problem
    Ahmad Biniaz, Anil Maheshwari, Michiel Smid and Paul Liu, pp. 262-267
    [Download PDF]
  • Bounds on Mutual Visibility Algorithms
    Gokarna Sharma, Costas Busch and Supratik Mukhopadhyay, pp. 268-274
    [Download PDF]

  • Session 6B
  • Buttons & Scissors is NP-Complete
    Harrison Gregg, Jody Leonard, Aaron Santiago and Aaron Williams, pp. 275-280
    [Download PDF]
  • Computational complexity of numberless Shakashaka
    Aviv Adler, Michael Biro, Erik Demaine, Mikhail Rudoy and Christiane Schmidt, pp. 281-286
    [Download PDF]
  • The Inapproximability of Illuminating Polygons by α-Floodlights
    Ahmed Abdelkader, Ahmed Saeed, Khaled Harras and Amr Mohamed, pp. 287-295
    [Download PDF]
  • Tradeoffs between Bends and Displacement in Anchored Graph Drawing
    Martin Fink and Subhash Suri, pp. 296-301
    [Download PDF]