SoCG 2015 June 22-25, 2015 - Eindhoven, The Netherlands

31st International Symposium on Computational Geometry (SoCG 2015)



Lars Arge and János Pach (Eds.)
ISBN 978-3-939897-83-5, LIPICS Vol. 34 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 34 MB)
Search Publication Server


Authors
  • Abam, Mohammad Ali
  • Abrahamsen, Mikkel
  • Adeli, Marjan
  • Agarwal, Pankaj K.
  • Ahn, Hee Kap
  • Albers, Susanne
  • Allen-Zhu, Zeyuan
  • Anagnostopoulos, Evangelos
  • Angelini, Patrizio
  • Arge, Lars
  • Arkin, Esther M.
  • Arya, Sunil
  • Asadollahpoor, Pooya Zafar
  • Awasthi, Pranjal
  • Balko, Martin
  • Barba, Luis
  • Barequet, Gill
  • Bauer, Ulrich
  • Becker, Aaron T.
  • Biedl, Therese
  • Boissonnat, Jean-Daniel
  • Bokal, Drago
  • Bos, Arie
  • Bose, Prosenjit
  • Bringmann, Karl
  • Buchet, Mickaël
  • Burton, Benjamin A.
  • Cabello, Sergio
  • Cardinal, Jean
  • Cavanna, Nicholas J.
  • Chan, Timothy M.
  • Chang, Hsien-Chih
  • Charikar, Moses
  • Chazal, Frédéric
  • Chen, Ho-Lin
  • Cohen-Addad, Vincent
  • Dadush, Daniel
  • Da Lozzo, Giordano
  • De Carufel, Jean-Lou
  • de Joannis de Verclos, Rémi
  • Demaine, Erik D.
  • Derka, Martin
  • Devillers, Olivier
  • Dey, Tamal K.
  • de Zeeuw, Frank
  • Dobbins, Michael Gene
  • Doty, David
  • Dutta, Kunal
  • Dvir, Zeev
  • Dyer, Ramsay
  • Efrat, Alon
  • Emiris, Ioannis Z.
  • Eppstein, David
  • Ezra, Esther
  • Fan, Fengtao
  • Fekete, Sándor P.
  • Felsner, Stefan
  • Franek, Peter
  • Frati, Fabrizio
  • Fukuda, Komei
  • Gärtner, Bernd
  • Gelashvili, Rati
  • Ghosh, Arijit
  • Glisse, Marc
  • Goaoc, Xavier
  • Gopi, Sivakanth
  • Goswami, Mayank
  • Green, Ben J.
  • Gu, Xianfeng
  • Hähnle, Nicolai
  • Har-Peled, Sariel
  • Haverkort, Herman J.
  • Hoffmann, Frank
  • Hoffmann, Udo
  • Holmsen, Andreas
  • Homapour, Hamid
  • Hu, Guangda
  • Hubard, Alfredo
  • Jahanseir, Mahmoodreza
  • Jelínek, Vít
  • Kaplan, Haim
  • Karavelas, Menelaos I.
  • Kiazyk, Stephen
  • Klein, Rolf
  • Knauer, Christian
  • Korman, Matias
  • Kostitsyna, Irina
  • Krcál, Marek
  • Kriegel, Klaus
  • Krishnaswamy, Ravishankar
  • Kumar, Nirman
  • Löffler, Maarten
  • Langetepe, Elmar
  • Levcopoulos, Christos
  • Lubiw, Anna
  • Lund, Ben
  • Mřlhave, Thomas
  • Mabillard, Isaac
  • Manuch, Ján
  • Mathieu, Claire
  • Matoušek, Jirí
  • Micek, Piotr
  • Mitchell, Joseph S. B.
  • Morris-Wright, Rose
  • Mount, David M.
  • Mulzer, Wolfgang
  • Munch, Elizabeth
  • Nikolov, Aleksandar
  • Oh, Eunjin
  • Oudot, Steve Y.
  • Pach, János
  • Park, Eunhui
  • Paták, Pavel
  • Patáková, Zuzana
  • Patrignani, Maurizio
  • Pettersson, William
  • Phillips, Jeff M.
  • Pilz, Alexander
  • Pingali, Vamsi P.
  • Polishchuk, Valentin
  • Psarros, Ioannis
  • Rafiey, Arash
  • Raichel, Benjamin
  • Raz, Orit E.
  • Razenshteyn, Ilya
  • Revsbćk, Morten
  • Roche-Newton, Oliver
  • Roditty, Liam
  • Roselli, Vincenzo
  • Rote, Günter
  • S., Karthik C.
  • Safa, Issam
  • Schlipf, Lena
  • Seiferth, Paul
  • Sereni, Jean-Sébastien
  • Shad, Hamed Mohtasham
  • Shalah, Mira
  • Sharir, Micha
  • Sheehy, Donald R.
  • Sheffer, Adam
  • Shi, Dayu
  • Sinop, Ali Kemal
  • Solomon, Noam
  • Speckmann, Bettina
  • Staals, Frank
  • Stacho, Ladislav
  • Stein, Yannik
  • Suk, Andrew
  • Suri, Subhash
  • Szedlák, May
  • Talvitie, Topi
  • Tancer, Martin
  • Tavenas, Sébastien
  • Telang, Gaurish
  • Thomasse, Rémy
  • Tsakalidis, Konstantinos
  • Tzanaki, Eleni
  • Ueckerdt, Torsten
  • Valtr, Pavel
  • van Kreveld, Marc
  • Vegter, Gert
  • Verbeek, Kevin
  • Volec, Jan
  • Wagner, Uli
  • Walczak, Bartosz
  • Wang, Bei
  • Wang, Yusu
  • Welzl, Emo
  • Willert, Max
  • Wintraecken, Mathijs
  • Yang, Jungwoo
  • Zheng, Yan

  •   
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Arge, Lars ; Pach, János

    Abstract | Document (679 KB) | BibTeX

    Combinatorial Discrepancy for Boxes via the gamma_2 Norm
    Authors: Matoušek, Jirí ; Nikolov, Aleksandar

    Abstract | Document (520 KB) | BibTeX

    Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals
    Authors: Becker, Aaron T. ; Demaine, Erik D. ; Fekete, Sándor P. ; Shad, Hamed Mohtasham ; Morris-Wright, Rose

    Abstract | Document (520 KB) | BibTeX

    Automatic Proofs for Formulae Enumerating Proper Polycubes
    Authors: Barequet, Gill ; Shalah, Mira

    Abstract | Document (390 KB) | BibTeX

    Visualizing Sparse Filtrations
    Authors: Cavanna, Nicholas J. ; Jahanseir, Mahmoodreza ; Sheehy, Donald R.

    Abstract | Document (862 KB) | BibTeX

    Visualizing Quickest Visibility Maps
    Authors: Talvitie, Topi

    Abstract | Document (317 KB) | BibTeX

    Sylvester-Gallai for Arrangements of Subspaces
    Authors: Dvir, Zeev ; Hu, Guangda

    Abstract | Document (483 KB) | BibTeX

    Computational Aspects of the Colorful Carathéodory Theorem
    Authors: Mulzer, Wolfgang ; Stein, Yannik

    Abstract | Document (597 KB) | BibTeX

    Semi-algebraic Ramsey Numbers
    Authors: Suk, Andrew

    Abstract | Document (479 KB) | BibTeX

    A Short Proof of a Near-Optimal Cardinality Estimate for the Product of a Sum Set
    Authors: Roche-Newton, Oliver

    Abstract | Document (401 KB) | BibTeX

    A Geometric Approach for the Upper Bound Theorem for Minkowski Sums of Convex Polytopes
    Authors: Karavelas, Menelaos I. ; Tzanaki, Eleni

    Abstract | Document (648 KB) | BibTeX

    Two Proofs for Shallow Packings
    Authors: Dutta, Kunal ; Ezra, Esther ; Ghosh, Arijit

    Abstract | Document (538 KB) | BibTeX

    Shortest Path in a Polygon using Sublinear Space
    Authors: Har-Peled, Sariel

    Abstract | Document (702 KB) | BibTeX

    Optimal Morphs of Convex Drawings
    Authors: Angelini, Patrizio ; Da Lozzo, Giordano ; Frati, Fabrizio ; Lubiw, Anna ; Patrignani, Maurizio ; Roselli, Vincenzo

    Abstract | Document (656 KB) | BibTeX

    1-String B_2-VPG Representation of Planar Graphs
    Authors: Biedl, Therese ; Derka, Martin

    Abstract | Document (680 KB) | BibTeX

    Spanners and Reachability Oracles for Directed Transmission Graphs
    Authors: Kaplan, Haim ; Mulzer, Wolfgang ; Roditty, Liam ; Seiferth, Paul

    Abstract | Document (539 KB) | BibTeX

    Recognition and Complexity of Point Visibility Graphs
    Authors: Cardinal, Jean ; Hoffmann, Udo

    Abstract | Document (592 KB) | BibTeX

    Geometric Spanners for Points Inside a Polygonal Domain
    Authors: Abam, Mohammad Ali ; Adeli, Marjan ; Homapour, Hamid ; Asadollahpoor, Pooya Zafar

    Abstract | Document (545 KB) | BibTeX

    An Optimal Algorithm for the Separating Common Tangents of Two Polygons
    Authors: Abrahamsen, Mikkel

    Abstract | Document (447 KB) | BibTeX

    A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon
    Authors: Ahn, Hee Kap ; Barba, Luis ; Bose, Prosenjit ; De Carufel, Jean-Lou ; Korman, Matias ; Oh, Eunjin

    Abstract | Document (589 KB) | BibTeX

    On the Smoothed Complexity of Convex Hulls
    Authors: Devillers, Olivier ; Glisse, Marc ; Goaoc, Xavier ; Thomasse, Rémy

    Abstract | Document (1,084 KB) | BibTeX

    Finding All Maximal Subsequences with Hereditary Properties
    Authors: Bokal, Drago ; Cabello, Sergio ; Eppstein, David

    Abstract | Document (536 KB) | BibTeX

    Riemannian Simplices and Triangulations
    Authors: Dyer, Ramsay ; Vegter, Gert ; Wintraecken, Mathijs

    Abstract | Document (497 KB) | BibTeX

    An Edge-Based Framework for Enumerating 3-Manifold Triangulations
    Authors: Burton, Benjamin A. ; Pettersson, William

    Abstract | Document (483 KB) | BibTeX

    Order on Order Types
    Authors: Pilz, Alexander ; Welzl, Emo

    Abstract | Document (540 KB) | BibTeX

    Limits of Order Types
    Authors: Goaoc, Xavier ; Hubard, Alfredo ; de Joannis de Verclos, Rémi ; Sereni, Jean-Sébastien ; Volec, Jan

    Abstract | Document (650 KB) | BibTeX

    Combinatorial Redundancy Detection
    Authors: Fukuda, Komei ; Gärtner, Bernd ; Szedlák, May

    Abstract | Document (466 KB) | BibTeX

    Effectiveness of Local Search for Geometric Optimization
    Authors: Cohen-Addad, Vincent ; Mathieu, Claire

    Abstract | Document (537 KB) | BibTeX

    On the Shadow Simplex Method for Curved Polyhedra
    Authors: Dadush, Daniel ; Hähnle, Nicolai

    Abstract | Document (506 KB) | BibTeX

    Pattern Overlap Implies Runaway Growth in Hierarchical Tile Systems
    Authors: Chen, Ho-Lin ; Doty, David ; Manuch, Ján ; Rafiey, Arash ; Stacho, Ladislav

    Abstract | Document (960 KB) | BibTeX

    Space Exploration via Proximity Search
    Authors: Har-Peled, Sariel ; Kumar, Nirman ; Mount, David M. ; Raichel, Benjamin

    Abstract | Document (709 KB) | BibTeX

    Star Unfolding from a Geodesic Curve
    Authors: Kiazyk, Stephen ; Lubiw, Anna

    Abstract | Document (1,176 KB) | BibTeX

    The Dirac-Motzkin Problem on Ordinary Lines and the Orchard Problem (Invited Talk)
    Authors: Green, Ben J.

    Abstract | Document (266 KB) | BibTeX

    On the Beer Index of Convexity and Its Variants
    Authors: Balko, Martin ; Jelínek, Vít ; Valtr, Pavel ; Walczak, Bartosz

    Abstract | Document (614 KB) | BibTeX

    Tight Bounds for Conflict-Free Chromatic Guarding of Orthogonal Art Galleries
    Authors: Hoffmann, Frank ; Kriegel, Klaus ; Suri, Subhash ; Verbeek, Kevin ; Willert, Max

    Abstract | Document (558 KB) | BibTeX

    Low-Quality Dimension Reduction and High-Dimensional Approximate Nearest Neighbor
    Authors: Anagnostopoulos, Evangelos ; Emiris, Ioannis Z. ; Psarros, Ioannis

    Abstract | Document (536 KB) | BibTeX

    Restricted Isometry Property for General p-Norms
    Authors: Allen-Zhu, Zeyuan ; Gelashvili, Rati ; Razenshteyn, Ilya

    Abstract | Document (501 KB) | BibTeX

    Strong Equivalence of the Interleaving and Functional Distortion Metrics for Reeb Graphs
    Authors: Bauer, Ulrich ; Munch, Elizabeth ; Wang, Yusu

    Abstract | Document (523 KB) | BibTeX

    On Generalized Heawood Inequalities for Manifolds: A Van Kampen-Flores-type Nonembeddability Result
    Authors: Goaoc, Xavier ; Mabillard, Isaac ; Paták, Pavel ; Patáková, Zuzana ; Tancer, Martin ; Wagner, Uli

    Abstract | Document (622 KB) | BibTeX

    Comparing Graphs via Persistence Distortion
    Authors: Dey, Tamal K. ; Shi, Dayu ; Wang, Yusu

    Abstract | Document (762 KB) | BibTeX

    Bounding Helly Numbers via Betti Numbers
    Authors: Goaoc, Xavier ; Paták, Pavel ; Patáková, Zuzana ; Tancer, Martin ; Wagner, Uli

    Abstract | Document (619 KB) | BibTeX

    Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited
    Authors: Raz, Orit E. ; Sharir, Micha ; de Zeeuw, Frank

    Abstract | Document (535 KB) | BibTeX

    Bisector Energy and Few Distinct Distances
    Authors: Lund, Ben ; Sheffer, Adam ; de Zeeuw, Frank

    Abstract | Document (586 KB) | BibTeX

    Incidences between Points and Lines in Three Dimensions
    Authors: Sharir, Micha ; Solomon, Noam

    Abstract | Document (546 KB) | BibTeX

    The Number of Unit-Area Triangles in the Plane: Theme and Variations
    Authors: Raz, Orit E. ; Sharir, Micha

    Abstract | Document (548 KB) | BibTeX

    On the Number of Rich Lines in Truly High Dimensional Sets
    Authors: Dvir, Zeev ; Gopi, Sivakanth

    Abstract | Document (472 KB) | BibTeX

    Realization Spaces of Arrangements of Convex Bodies
    Authors: Dobbins, Michael Gene ; Holmsen, Andreas ; Hubard, Alfredo

    Abstract | Document (568 KB) | BibTeX

    Computing Teichmüller Maps between Polygons
    Authors: Goswami, Mayank ; Gu, Xianfeng ; Pingali, Vamsi P. ; Telang, Gaurish

    Abstract | Document (649 KB) | BibTeX

    On-line Coloring between Two Lines
    Authors: Felsner, Stefan ; Micek, Piotr ; Ueckerdt, Torsten

    Abstract | Document (537 KB) | BibTeX

    Building Efficient and Compact Data Structures for Simplicial Complexes
    Authors: Boissonnat, Jean-Daniel ; S., Karthik C. ; Tavenas, Sébastien

    Abstract | Document (613 KB) | BibTeX

    Shortest Path to a Segment and Quickest Visibility Queries
    Authors: Arkin, Esther M. ; Efrat, Alon ; Knauer, Christian ; Mitchell, Joseph S. B. ; Polishchuk, Valentin ; Rote, Günter ; Schlipf, Lena ; Talvitie, Topi

    Abstract | Document (673 KB) | BibTeX

    Trajectory Grouping Structure under Geodesic Distance
    Authors: Kostitsyna, Irina ; van Kreveld, Marc ; Löffler, Maarten ; Speckmann, Bettina ; Staals, Frank

    Abstract | Document (675 KB) | BibTeX

    From Proximity to Utility: A Voronoi Partition of Pareto Optima
    Authors: Chang, Hsien-Chih ; Har-Peled, Sariel ; Raichel, Benjamin

    Abstract | Document (586 KB) | BibTeX

    Faster Deterministic Volume Estimation in the Oracle Model via Thin Lattice Coverings
    Authors: Dadush, Daniel

    Abstract | Document (407 KB) | BibTeX

    Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
    Authors: Chan, Timothy M. ; Tsakalidis, Konstantinos

    Abstract | Document (550 KB) | BibTeX

    A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions
    Authors: Chan, Timothy M.

    Abstract | Document (339 KB) | BibTeX

    Approximability of the Discrete Fréchet Distance
    Authors: Bringmann, Karl ; Mulzer, Wolfgang

    Abstract | Document (552 KB) | BibTeX

    The Hardness of Approximation of Euclidean k-Means
    Authors: Awasthi, Pranjal ; Charikar, Moses ; Krishnaswamy, Ravishankar ; Sinop, Ali Kemal

    Abstract | Document (529 KB) | BibTeX

    A Fire Fighter’s Problem
    Authors: Klein, Rolf ; Langetepe, Elmar ; Levcopoulos, Christos

    Abstract | Document (757 KB) | BibTeX

    Approximate Geometric MST Range Queries
    Authors: Arya, Sunil ; Mount, David M. ; Park, Eunhui

    Abstract | Document (541 KB) | BibTeX

    Maintaining Contour Trees of Dynamic Terrains
    Authors: Agarwal, Pankaj K. ; Mřlhave, Thomas ; Revsbćk, Morten ; Safa, Issam ; Wang, Yusu ; Yang, Jungwoo

    Abstract | Document (1,194 KB) | BibTeX

    Hyperorthogonal Well-Folded Hilbert Curves
    Authors: Bos, Arie ; Haverkort, Herman J.

    Abstract | Document (592 KB) | BibTeX

    Topological Analysis of Scalar Fields with Outliers
    Authors: Buchet, Mickaël ; Chazal, Frédéric ; Dey, Tamal K. ; Fan, Fengtao ; Oudot, Steve Y. ; Wang, Yusu

    Abstract | Document (532 KB) | BibTeX

    On Computability and Triviality of Well Groups
    Authors: Franek, Peter ; Krcál, Marek

    Abstract | Document (609 KB) | BibTeX

    Geometric Inference on Kernel Density Estimates
    Authors: Phillips, Jeff M. ; Wang, Bei ; Zheng, Yan

    Abstract | Document (1,866 KB) | BibTeX

    Modeling Real-World Data Sets (Invited Talk)
    Authors: Albers, Susanne

    Abstract | Document (203 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint Published by LZI