Portal - SoCG 2016

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

Bhattiprolu, Vijay V. S. P.

da Fonseca, Guilherme D.

Dobbins, Michael Gene

Dotterrer, Dominic

Dumitrescu, Adrian

Eisenbrand, Friedrich

Hosseini, Seyed Hossein

Hsu, Ching-Hsiang

Hubard, Alfredo

Iacono, John

Igamberdiev, Alexander

Montecchiani, Fabrizio

Shewchuk, Jonathan Richard

Sindahl Nielsen, Jesper

Wulff-Nilsen, Christian

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

32nd International Symposium on Computational Geometry (SoCG 2016)