Portal - SoCG 2015

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

Anagnostopoulos, Evangelos

Asadollahpoor, Pooya Zafar

Boissonnat, Jean-Daniel

de Joannis de Verclos, Rémi

Dobbins, Michael Gene

Jahanseir, Mahmoodreza

Jelínek, Vít

Kaplan, Haim

Karavelas, Menelaos I.

Krishnaswamy, Ravishankar

Kumar, Nirman

Langetepe, Elmar

Levcopoulos, Christos

Mitchell, Joseph S. B.

Sereni, Jean-Sébastien

Shad, Hamed Mohtasham

Tsakalidis, Konstantinos

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 | Privacy Published by LZI

31st International Symposium on Computational Geometry (SoCG 2015)