SoCG 2016 June 14-18, 2016 - Boston, USA

32nd International Symposium on Computational Geometry (SoCG 2016)



Sándor Fekete and Anna Lubiw (Eds.)
ISBN 978-3-95977-009-5, LIPICS Vol. 51 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 49 MB)
Search Publication Server


Authors
  • Abel, Zachary
  • Abrahamsen, Mikkel
  • Ackerman, Eyal
  • Afshani, Peyman
  • Agarwal, Pankaj K.
  • Ahn, Hee-Kap
  • Aichholzer, Oswin
  • Akitaya, Hugo A.
  • Allen, Sarah R.
  • Aloupis, Greg
  • Alvarez, Victor
  • Andoni, Alexandr
  • Aronov, Boris
  • Arya, Sunil
  • Asselin, Lynn
  • Bae, Sang Won
  • Bagchi, Bhaskar
  • Balas, Kevin
  • Bandyapadhyay, Sayan
  • Barba, Luis
  • Bartal, Yair
  • Bendich, Paul
  • Berglin, Edvin
  • Berman, Piotr
  • Bhattiprolu, Vijay V. S. P.
  • Biedl, Therese
  • Bogdanov, Mikhail
  • Bohler, Cecilia
  • Borradaile, Glencora
  • Burton, Benjamin A.
  • Carričre, Mathieu
  • Cevallos, Alfonso
  • Chambers, Erin Wolf
  • Chan, Timothy M.
  • Chang, Hsien-Chih
  • Cheng, Siu-Wing
  • Cheong, Otfried
  • Chimani, Markus
  • Choudhary, Aruni
  • Cook IV, Atlas F.
  • da Fonseca, Guilherme D.
  • Datta, Basudeb
  • de Berg, Mark
  • Demaine, Erik D.
  • Demaine, Martin L.
  • de Mesmay, Arnaud
  • Dernár, Marek
  • Devadoss, Satyan
  • Devillers, Olivier
  • Ding, Hu
  • Dobbins, Michael Gene
  • Dotterrer, Dominic
  • Dumitrescu, Adrian
  • Eisenbrand, Friedrich
  • Eisenstat, Sarah
  • Eppstein, David
  • Epstein, Ziv
  • Erickson, Jeff
  • Farshi, Mohammad
  • Fekete, Sándor
  • Felsner, Stefan
  • Fink, Martin
  • Fomin, Fedor
  • Fox, Jacob
  • Fox, Kyle
  • Gärtner, Bernd
  • Gao, Jing
  • Gardner, Kirk
  • Gasparovic, Ellen
  • Geraerts, Roland
  • Geyer, Markus
  • Goaoc, Xavier
  • Gottlieb, Lee-Ad
  • Gudmundsson, Joachim
  • Hackl, Thomas
  • Har-Peled, Sariel
  • Harer, John
  • Hershberger, John
  • Hlinený, Petr
  • Hoffmann, Michael
  • Hosseini, Seyed Hossein
  • Hsu, Ching-Hsiang
  • Hubard, Alfredo
  • Iacono, John
  • Igamberdiev, Alexander
  • Indyk, Piotr
  • Janardan, Ravi
  • Jiang, Minghui
  • Kaluža, Vojtech
  • Kanj, Iyad
  • Karavelas, Menelaos
  • Kaufman, Tali
  • Kaufmann, Michael
  • Kawamura, Akitoshi
  • Kerber, Michael
  • Keszegh, Balázs
  • Khoury, Marc
  • Kim, Heuna
  • Kindermann, Philipp
  • Klein, Rolf
  • Kleinberg, Robert
  • Klemz, Boris
  • Kolay, Sudeshna
  • Kostitsyna, Irina
  • Kumar, Nirman
  • Kupavskii, Andrey
  • Kusters, Vincent
  • Löffler, Maarten
  • Langerman, Stefan
  • Lengler, Johannes
  • Li, Yuan
  • Liotta, Giuseppe
  • Liu, Chih-Hung
  • Lokshtanov, Daniel
  • Lubiw, Anna
  • Lynch, Jayson
  • Mabillard, Isaac
  • Mahabadi, Sepideh
  • Marx, Dániel
  • Mchedlidze, Tamara
  • Mehr, Mehran
  • Miltzow, Tillmann
  • Montecchiani, Fabrizio
  • Moriyama, Sonoko
  • Mount, David M.
  • Munch, Elizabeth
  • Murzabulatov, Meiram
  • Mustafa, Nabil
  • Nayyeri, Amir
  • Oh, Eunjin
  • Otachi, Yota
  • Oudot, Steve
  • Pach, János
  • Pan, Jiangwei
  • Panolan, Fahad
  • Perkovic, Ljubomir
  • Pilz, Alexander
  • Polishchuk, Valentin
  • Pratt, Kevin
  • Pratt, Simon
  • Raghvendra, Sharath
  • Raichel, Benjamin
  • Raskhodnikova, Sofya
  • Raz, Orit E.
  • Razensteyn, Ilya
  • Riley, Connor
  • Rok, Alexandre
  • Rote, Günter
  • Rus, Daniela
  • Ryan, John Paul
  • Saurabh, Saket
  • Schardl, Tao B.
  • Scheucher, Manfred
  • Seshadhri, C.
  • Sheehy, Donald
  • Shewchuk, Jonathan Richard
  • Sindahl Nielsen, Jesper
  • Singh, Nitin
  • Smirnov, Dmitriy
  • Smorodinsky, Shakhar
  • Speckmann, Bettina
  • Spreer, Jonathan
  • Staals, Frank
  • Suri, Subhash
  • Szedlák, May
  • Tóth, Csaba
  • Türkoglu, Duru
  • Tancer, Martin
  • Teillaud, Monique
  • Thorup, Mikkel
  • Tralie, Christopher
  • van Duijn, Ingo
  • van Goethem, Arthur
  • van Kreveld, Marc
  • van Toll, Wouter
  • Varadarajan, Kasturi
  • Vegter, Gert
  • Vizer, Máté
  • Vogtenhuber, Birgit
  • Wagner, Uli
  • Wang, Bei
  • Wilkinson, Bryan T.
  • Winslow, Andrew
  • Wright, Matthew L.
  • Wulff-Nilsen, Christian
  • Xu, Hanzhong
  • Xu, Jinhui
  • Xue, Jie
  • Yap, Chee
  • Ying, Rex
  • Yon, Juyoung
  • Yuan, Yang
  • Zenklusen, Rico

  •   
    Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors
    Authors: Fekete, Sándor ; Lubiw, Anna

    Abstract | Document (4,789 KB) | BibTeX

    Toward Pervasive Robots (Invited Talk)
    Authors: Rus, Daniela

    Abstract | Document (199 KB) | BibTeX

    Discrete Geometry, Algebra, and Combinatorics (Invited Talk)
    Authors: Fox, Jacob

    Abstract | Document (197 KB) | BibTeX

    Who Needs Crossings? Hardness of Plane Graph Rigidity
    Authors: Abel, Zachary ; Demaine, Erik D. ; Demaine, Martin L. ; Eisenstat, Sarah ; Lynch, Jayson ; Schardl, Tao B.

    Abstract | Document (685 KB) | BibTeX

    Finding the Maximum Subset with Bounded Convex Curvature
    Authors: Abrahamsen, Mikkel ; Thorup, Mikkel

    Abstract | Document (606 KB) | BibTeX

    Coloring Points with Respect to Squares
    Authors: Ackerman, Eyal ; Keszegh, Balázs ; Vizer, Máté

    Abstract | Document (604 KB) | BibTeX

    Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences
    Authors: Agarwal, Pankaj K. ; Fox, Kyle ; Pan, Jiangwei ; Ying, Rex

    Abstract | Document (695 KB) | BibTeX

    An Improved Lower Bound on the Minimum Number of Triangulations
    Authors: Aichholzer, Oswin ; Alvarez, Victor ; Hackl, Thomas ; Pilz, Alexander ; Speckmann, Bettina ; Vogtenhuber, Birgit

    Abstract | Document (737 KB) | BibTeX

    Recognizing Weakly Simple Polygons
    Authors: Akitaya, Hugo A. ; Aloupis, Greg ; Erickson, Jeff ; Tóth, Csaba

    Abstract | Document (786 KB) | BibTeX

    Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing
    Authors: Andoni, Alexandr ; Razensteyn, Ilya

    Abstract | Document (444 KB) | BibTeX

    The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions
    Authors: Aronov, Boris ; Cheong, Otfried ; Dobbins, Michael Gene ; Goaoc, Xavier

    Abstract | Document (605 KB) | BibTeX

    On the Combinatorial Complexity of Approximating Polytopes
    Authors: Arya, Sunil ; da Fonseca, Guilherme D. ; Mount, David M.

    Abstract | Document (696 KB) | BibTeX

    Efficient Algorithms to Decide Tightness
    Authors: Bagchi, Bhaskar ; Datta, Basudeb ; Burton, Benjamin A. ; Singh, Nitin ; Spreer, Jonathan

    Abstract | Document (584 KB) | BibTeX

    Anchored Rectangle and Square Packings
    Authors: Balas, Kevin ; Dumitrescu, Adrian ; Tóth, Csaba

    Abstract | Document (619 KB) | BibTeX

    On Variants of k-means Clustering
    Authors: Bandyapadhyay, Sayan ; Varadarajan, Kasturi

    Abstract | Document (520 KB) | BibTeX

    Incremental Voronoi diagrams
    Authors: Allen, Sarah R. ; Barba, Luis ; Iacono, John ; Langerman, Stefan

    Abstract | Document (628 KB) | BibTeX

    Dimension Reduction Techniques for l_p (1
    Authors: Bartal, Yair ; Gottlieb, Lee-Ad

    Abstract | Document (566 KB) | BibTeX

    Testing Convexity of Figures Under the Uniform Distribution
    Authors: Berman, Piotr ; Murzabulatov, Meiram ; Raskhodnikova, Sofya

    Abstract | Document (2,029 KB) | BibTeX

    Separating a Voronoi Diagram via Local Search
    Authors: Bhattiprolu, Vijay V. S. P. ; Har-Peled, Sariel

    Abstract | Document (810 KB) | BibTeX

    On Visibility Representations of Non-Planar Graphs
    Authors: Biedl, Therese ; Liotta, Giuseppe ; Montecchiani, Fabrizio

    Abstract | Document (572 KB) | BibTeX

    Delaunay Triangulations on Orientable Surfaces of Low Genus
    Authors: Bogdanov, Mikhail ; Teillaud, Monique ; Vegter, Gert

    Abstract | Document (1,176 KB) | BibTeX

    An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams
    Authors: Bohler, Cecilia ; Klein, Rolf ; Liu, Chih-Hung

    Abstract | Document (694 KB) | BibTeX

    All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs
    Authors: Borradaile, Glencora ; Eppstein, David ; Nayyeri, Amir ; Wulff-Nilsen, Christian

    Abstract | Document (581 KB) | BibTeX

    Minimum Cycle and Homology Bases of Surface Embedded Graphs
    Authors: Borradaile, Glencora ; Chambers, Erin Wolf ; Fox, Kyle ; Nayyeri, Amir

    Abstract | Document (566 KB) | BibTeX

    Finding Non-Orientable Surfaces in 3-Manifolds
    Authors: Burton, Benjamin A. ; de Mesmay, Arnaud ; Wagner, Uli

    Abstract | Document (561 KB) | BibTeX

    Structure and Stability of the 1-Dimensional Mapper
    Authors: Carričre, Mathieu ; Oudot, Steve

    Abstract | Document (617 KB) | BibTeX

    Max-Sum Diversity Via Convex Programming
    Authors: Cevallos, Alfonso ; Eisenbrand, Friedrich ; Zenklusen, Rico

    Abstract | Document (514 KB) | BibTeX

    Dynamic Streaming Algorithms for Epsilon-Kernels
    Authors: Chan, Timothy M.

    Abstract | Document (518 KB) | BibTeX

    Two Approaches to Building Time-Windowed Geometric Data Structures
    Authors: Chan, Timothy M. ; Pratt, Simon

    Abstract | Document (532 KB) | BibTeX

    Untangling Planar Curves
    Authors: Chang, Hsien-Chih ; Erickson, Jeff

    Abstract | Document (4,714 KB) | BibTeX

    Inserting Multiple Edges into a Planar Graph
    Authors: Chimani, Markus ; Hlinený, Petr

    Abstract | Document (579 KB) | BibTeX

    Polynomial-Sized Topological Approximations Using the Permutahedron
    Authors: Choudhary, Aruni ; Kerber, Michael ; Raghvendra, Sharath

    Abstract | Document (520 KB) | BibTeX

    Faster Algorithms for Computing Plurality Points
    Authors: de Berg, Mark ; Gudmundsson, Joachim ; Mehr, Mehran

    Abstract | Document (526 KB) | BibTeX

    Qualitative Symbolic Perturbation
    Authors: Devillers, Olivier ; Karavelas, Menelaos ; Teillaud, Monique

    Abstract | Document (1,113 KB) | BibTeX

    Finding Global Optimum for Truth Discovery: Entropy Based Geometric Variance
    Authors: Ding, Hu ; Gao, Jing ; Xu, Jinhui

    Abstract | Document (710 KB) | BibTeX

    On Expansion and Topological Overlap
    Authors: Dotterrer, Dominic ; Kaufman, Tali ; Wagner, Uli

    Abstract | Document (524 KB) | BibTeX

    On the Number of Maximum Empty Boxes Amidst n Points
    Authors: Dumitrescu, Adrian ; Jiang, Minghui

    Abstract | Document (546 KB) | BibTeX

    Strongly Monotone Drawings of Planar Graphs
    Authors: Felsner, Stefan ; Igamberdiev, Alexander ; Kindermann, Philipp ; Klemz, Boris ; Mchedlidze, Tamara ; Scheucher, Manfred

    Abstract | Document (611 KB) | BibTeX

    Hyperplane Separability and Convexity of Probabilistic Point Sets
    Authors: Fink, Martin ; Hershberger, John ; Kumar, Nirman ; Suri, Subhash

    Abstract | Document (525 KB) | BibTeX

    Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems
    Authors: Fomin, Fedor ; Kolay, Sudeshna ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket

    Abstract | Document (548 KB) | BibTeX

    Random Sampling with Removal
    Authors: Gärtner, Bernd ; Lengler, Johannes ; Szedlák, May

    Abstract | Document (526 KB) | BibTeX

    The Planar Tree Packing Theorem
    Authors: Geyer, Markus ; Hoffmann, Michael ; Kaufmann, Michael ; Kusters, Vincent ; Tóth, Csaba

    Abstract | Document (637 KB) | BibTeX

    Crossing Number is Hard for Kernelization
    Authors: Hlinený, Petr ; Dernár, Marek

    Abstract | Document (487 KB) | BibTeX

    Shortest Path Embeddings of Graphs on Surfaces
    Authors: Hubard, Alfredo ; Kaluža, Vojtech ; de Mesmay, Arnaud ; Tancer, Martin

    Abstract | Document (584 KB) | BibTeX

    Simultaneous Nearest Neighbor Search
    Authors: Indyk, Piotr ; Kleinberg, Robert ; Mahabadi, Sepideh ; Yuan, Yang

    Abstract | Document (2,544 KB) | BibTeX

    Degree Four Plane Spanners: Simpler and Better
    Authors: Kanj, Iyad ; Perkovic, Ljubomir ; Türkoglu, Duru

    Abstract | Document (561 KB) | BibTeX

    A Lower Bound on Opaque Sets
    Authors: Kawamura, Akitoshi ; Moriyama, Sonoko ; Otachi, Yota ; Pach, János

    Abstract | Document (569 KB) | BibTeX

    Fixed Points of the Restricted Delaunay Triangulation Operator
    Authors: Khoury, Marc ; Shewchuk, Jonathan Richard

    Abstract | Document (434 KB) | BibTeX

    Congruence Testing of Point Sets in 4-Space
    Authors: Kim, Heuna ; Rote, Günter

    Abstract | Document (549 KB) | BibTeX

    On the Complexity of Minimum-Link Path Problems
    Authors: Kostitsyna, Irina ; Löffler, Maarten ; Polishchuk, Valentin ; Staals, Frank

    Abstract | Document (644 KB) | BibTeX

    A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino
    Authors: Langerman, Stefan ; Winslow, Andrew

    Abstract | Document (593 KB) | BibTeX

    Eliminating Higher-Multiplicity Intersections, II. The Deleted Product Criterion in the r-Metastable Range
    Authors: Mabillard, Isaac ; Wagner, Uli

    Abstract | Document (608 KB) | BibTeX

    Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems
    Authors: Marx, Dániel ; Miltzow, Tillmann

    Abstract | Document (584 KB) | BibTeX

    Convergence between Categorical Representations of Reeb Space and Mapper
    Authors: Munch, Elizabeth ; Wang, Bei

    Abstract | Document (756 KB) | BibTeX

    New Lower Bounds for epsilon-Nets
    Authors: Kupavskii, Andrey ; Mustafa, Nabil ; Pach, János

    Abstract | Document (539 KB) | BibTeX

    On Computing the Fréchet Distance Between Surfaces
    Authors: Nayyeri, Amir ; Xu, Hanzhong

    Abstract | Document (575 KB) | BibTeX

    The Farthest-Point Geodesic Voronoi Diagram of Points on the Boundary of a Simple Polygon
    Authors: Oh, Eunjin ; Barba, Luis ; Ahn, Hee-Kap

    Abstract | Document (610 KB) | BibTeX

    Avoiding the Global Sort: A Faster Contour Tree Algorithm
    Authors: Raichel, Benjamin ; Seshadhri, C.

    Abstract | Document (475 KB) | BibTeX

    Configurations of Lines in 3-Space and Rigidity of Planar Structures
    Authors: Raz, Orit E.

    Abstract | Document (479 KB) | BibTeX

    Weak 1/r-Nets for Moving Points
    Authors: Rok, Alexandre ; Smorodinsky, Shakhar

    Abstract | Document (524 KB) | BibTeX

    Applications of Incidence Bounds in Point Covering Problems
    Authors: Afshani, Peyman ; Berglin, Edvin ; van Duijn, Ingo ; Sindahl Nielsen, Jesper

    Abstract | Document (547 KB) | BibTeX

    Grouping Time-Varying Data for Interactive Exploration
    Authors: van Goethem, Arthur ; van Kreveld, Marc ; Löffler, Maarten ; Speckmann, Bettina ; Staals, Frank

    Abstract | Document (626 KB) | BibTeX

    On the Separability of Stochastic Geometric Objects, with Applications
    Authors: Xue, Jie ; Li, Yuan ; Janardan, Ravi

    Abstract | Document (595 KB) | BibTeX

    Approximating Convex Shapes With Respect to Symmetric Difference Under Homotheties
    Authors: Yon, Juyoung ; Bae, Sang Won ; Cheng, Siu-Wing ; Cheong, Otfried ; Wilkinson, Bryan T.

    Abstract | Document (496 KB) | BibTeX

    Interactive Geometric Algorithm Visualization in a Browser
    Authors: Gardner, Kirk ; Asselin, Lynn ; Sheehy, Donald

    Abstract | Document (417 KB) | BibTeX

    Geometric Models for Musical Audio Data
    Authors: Bendich, Paul ; Gasparovic, Ellen ; Harer, John ; Tralie, Christopher

    Abstract | Document (931 KB) | BibTeX

    Visualizing Scissors Congruence
    Authors: Devadoss, Satyan ; Epstein, Ziv ; Smirnov, Dmitriy

    Abstract | Document (462 KB) | BibTeX

    Visualization of Geometric Spanner Algorithms
    Authors: Farshi, Mohammad ; Hosseini, Seyed Hossein

    Abstract | Document (406 KB) | BibTeX

    Path Planning for Simple Robots using Soft Subdivision Search
    Authors: Hsu, Ching-Hsiang ; Ryan, John Paul ; Yap, Chee

    Abstract | Document (451 KB) | BibTeX

    Exploring Circle Packing Algorithms
    Authors: Pratt, Kevin ; Riley, Connor ; Sheehy, Donald

    Abstract | Document (601 KB) | BibTeX

    The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation
    Authors: van Toll, Wouter ; Cook IV, Atlas F. ; van Kreveld, Marc ; Geraerts, Roland

    Abstract | Document (591 KB) | BibTeX

    High-Dimensional Geometry of Sliding Window Embeddings of Periodic Videos
    Authors: Tralie, Christopher

    Abstract | Document (2,762 KB) | BibTeX

    Introduction to Persistent Homology
    Authors: Wright, Matthew L.

    Abstract | Document (800 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint Published by LZI