Portal - SoCG 2018

SoCG 2018	June 11-14, 2018 - Budapest, Hungary
34th International Symposium on Computational Geometry (SoCG 2018) Bettina Speckmann and Csaba D. Tóth (Eds.)
ISBN 978-3-95977-066-8, LIPICS Vol. 99	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 53 MB)
Search Publication Server

Authors

Bjerkevik, Håvard Bakke

Boissonnat, Jean-Daniel

Edelsbrunner, Herbert

Fisikopoulos, Vissarion

Martínez-Sandoval, Leonardo

Mohammed, Abdulhakeem

Papadopoulou, Evanthia

Roldán-Pensado, Edgardo

Sidiropoulos, Anastasios

Tsakalidis, Konstantinos

Verdière, Éric Colin de

Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks

Authors: Speckmann, Bettina ; Tóth, Csaba D.

Abstract | Document (397 KB) | BibTeX

Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm

Authors: Abdelkader, Ahmed ; Bajaj, Chandrajit L. ; Ebeida, Mohamed S. ; Mahmoud, Ahmed H. ; Mitchell, Scott A. ; Owens, John D. ; Rushdi, Ahmad A.

Abstract | Document (3,468 KB) | BibTeX

Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs

Authors: Abu-Affash, A. Karim ; Carmi, Paz ; Maheshwari, Anil ; Morin, Pat ; Smid, Michiel ; Smorodinsky, Shakhar

Abstract | Document (649 KB) | BibTeX

Vietoris-Rips and Cech Complexes of Metric Gluings

Authors: Adamaszek, Michal ; Adams, Henry ; Gasparovic, Ellen ; Gommel, Maria ; Purvine, Emilie ; Sazdanovic, Radmila ; Wang, Bei ; Wang, Yusu ; Ziegelmeier, Lori

Abstract | Document (609 KB) | BibTeX

Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon

Authors: Agarwal, Pankaj K. ; Arge, Lars ; Staals, Frank

Abstract | Document (585 KB) | BibTeX

O~(n^{1/3})-Space Algorithm for the Grid Graph Reachability Problem

Authors: Ashida, Ryo ; Nakagawa, Kotaro

Abstract | Document (653 KB) | BibTeX

The Reverse Kakeya Problem

Authors: Bae, Sang Won ; Cabello, Sergio ; Cheong, Otfried ; Choi, Yoonsung ; Stehn, Fabian ; Yoon, Sang Duk

Abstract | Document (599 KB) | BibTeX

Capacitated Covering Problems in Geometric Spaces

Authors: Bandyapadhyay, Sayan ; Bhowmick, Santanu ; Inamdar, Tanmay ; Varadarajan, Kasturi

Abstract | Document (383 KB) | BibTeX

Faster Algorithms for some Optimization Problems on Collinear Points

Authors: Biniaz, Ahmad ; Bose, Prosenjit ; Carmi, Paz ; Maheshwari, Anil ; Munro, Ian ; Smid, Michiel

Abstract | Document (801 KB) | BibTeX

Local Criteria for Triangulation of Manifolds

Authors: Boissonnat, Jean-Daniel ; Dyer, Ramsay ; Ghosh, Arijit ; Wintraecken, Mathijs

Abstract | Document (493 KB) | BibTeX

The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces

Authors: Boissonnat, Jean-Daniel ; Lieutier, André ; Wintraecken, Mathijs

Abstract | Document (722 KB) | BibTeX

Orthogonal Terrain Guarding is NP-complete

Authors: Bonnet, Édouard ; Giannopoulos, Panos

Abstract | Document (486 KB) | BibTeX

QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs

Authors: Bonnet, Édouard ; Giannopoulos, Panos ; Kim, Eun Jung ; Rzazewski, Pawel ; Sikora, Florian

Abstract | Document (497 KB) | BibTeX

Computational Complexity of the Interleaving Distance

Authors: Bjerkevik, Håvard Bakke ; Botnan, Magnus Bakke

Abstract | Document (545 KB) | BibTeX

Sheaf-Theoretic Stratification Learning

Authors: Brown, Adam ; Wang, Bei

Abstract | Document (510 KB) | BibTeX

Realizations of Indecomposable Persistence Modules of Arbitrarily Large Dimension

Authors: Buchet, Mickaël ; Escolar, Emerson G.

Abstract | Document (491 KB) | BibTeX

Approximating the Distribution of the Median and other Robust Estimators on Uncertain Data

Authors: Buchin, Kevin ; Phillips, Jeff M. ; Tang, Pingfan

Abstract | Document (592 KB) | BibTeX

Consistent Sets of Lines with no Colorful Incidence

Authors: Bukh, Boris ; Goaoc, Xavier ; Hubard, Alfredo ; Trager, Matthew

Abstract | Document (1,041 KB) | BibTeX

The HOMFLY-PT Polynomial is Fixed-Parameter Tractable

Authors: Burton, Benjamin A.

Abstract | Document (1,029 KB) | BibTeX

Practical Volume Computation of Structured Convex Bodies, and an Application to Modeling Portfolio Dependencies and Financial Crises

Authors: Calès, Ludovic ; Chalkis, Apostolos ; Emiris, Ioannis Z. ; Fisikopoulos, Vissarion

Abstract | Document (751 KB) | BibTeX

Subquadratic Encodings for Point Configurations

Authors: Cardinal, Jean ; Chan, Timothy M. ; Iacono, John ; Langerman, Stefan ; Ooms, Aurélien

Abstract | Document (601 KB) | BibTeX

Algorithms for Low-Distortion Embeddings into Arbitrary 1-Dimensional Spaces

Authors: Carpenter, Timothy ; Fomin, Fedor V. ; Lokshtanov, Daniel ; Saurabh, Saket ; Sidiropoulos, Anastasios

Abstract | Document (450 KB) | BibTeX

Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs

Authors: Chalopin, Jérémie ; Chepoi, Victor ; Dragan, Feodor F. ; Ducoffe, Guillaume ; Mohammed, Abdulhakeem ; Vaxès, Yann

Abstract | Document (493 KB) | BibTeX

Tree Drawings Revisited

Authors: Chan, Timothy M.

Abstract | Document (580 KB) | BibTeX

Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs

Authors: Chan, Timothy M. ; Skrepetos, Dimitrios

Abstract | Document (483 KB) | BibTeX

Dynamic Planar Orthogonal Point Location in Sublogarithmic Time

Authors: Chan, Timothy M. ; Tsakalidis, Konstantinos

Abstract | Document (434 KB) | BibTeX

The Density of Expected Persistence Diagrams and its Kernel Based Estimation

Authors: Chazal, Frédéric ; Divol, Vincent

Abstract | Document (803 KB) | BibTeX

Embedding Graphs into Two-Dimensional Simplicial Complexes

Authors: Verdière, Éric Colin de ; Magnard, Thomas ; Mohar, Bojan

Abstract | Document (465 KB) | BibTeX

On the Complexity of Closest Pair via Polar-Pair of Point-Sets

Authors: David, Roee ; C. S., Karthik ; Laekhanukit, Bundit

Abstract | Document (580 KB) | BibTeX

Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch

Authors: Demaine, Erik D. ; Fekete, Sándor P. ; Keldenich, Phillip ; Scheffer, Christian ; Meijer, Henk

Abstract | Document (577 KB) | BibTeX

3D Snap Rounding

Authors: Devillers, Olivier ; Lazard, Sylvain ; Lenhart, William J.

Abstract | Document (782 KB) | BibTeX

Graph Reconstruction by Discrete Morse Theory

Authors: Dey, Tamal K. ; Wang, Jiayuan ; Wang, Yusu

Abstract | Document (1,515 KB) | BibTeX

Computing Bottleneck Distance for 2-D Interval Decomposable Modules

Authors: Dey, Tamal K. ; Xin, Cheng

Abstract | Document (827 KB) | BibTeX

Structure and Generation of Crossing-Critical Graphs

Authors: Dvorák, Zdenek ; Hlinený, Petr ; Mohar, Bojan

Abstract | Document (568 KB) | BibTeX

The Multi-cover Persistence of Euclidean Balls

Authors: Edelsbrunner, Herbert ; Osang, Georg

Abstract | Document (516 KB) | BibTeX

Smallest Enclosing Spheres and Chernoff Points in BregmanGeometry

Authors: Edelsbrunner, Herbert ; Virk, Ziga ; Wagner, Hubert

Abstract | Document (478 KB) | BibTeX

Near Isometric Terminal Embeddings for Doubling Metrics

Authors: Elkin, Michael ; Neiman, Ofer

Abstract | Document (492 KB) | BibTeX

Products of Euclidean Metrics and Applications to Proximity Questions among Curves

Authors: Emiris, Ioannis Z. ; Psarros, Ioannis

Abstract | Document (490 KB) | BibTeX

Rainbow Cycles in Flip Graphs

Authors: Felsner, Stefan ; Kleist, Linda ; Mütze, Torsten ; Sering, Leon

Abstract | Document (998 KB) | BibTeX

Hanani-Tutte for Approximating Maps of Graphs

Authors: Fulek, Radoslav ; Kyncl, Jan

Abstract | Document (702 KB) | BibTeX

The Z_2-Genus of Kuratowski Minors

Authors: Fulek, Radoslav ; Kyncl, Jan

Abstract | Document (504 KB) | BibTeX

Shellability is NP-Complete

Authors: Goaoc, Xavier ; Paták, Pavel ; Patáková, Zuzana ; Tancer, Martin ; Wagner, Uli

Abstract | Document (702 KB) | BibTeX

Optimal Morphs of Planar Orthogonal Drawings

Authors: van Goethem, Arthur ; Verbeek, Kevin

Abstract | Document (807 KB) | BibTeX

Computational Topology and the Unique Games Conjecture

Authors: Grochow, Joshua A. ; Tucker-Foltz, Jamie

Abstract | Document (500 KB) | BibTeX

Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality

Authors: Haas, Andreas

Abstract | Document (538 KB) | BibTeX

Dynamic Smooth Compressed Quadtrees

Authors: van der Hoog, Ivor ; Khramtcova, Elena ; Löffler, Maarten

Abstract | Document (635 KB) | BibTeX

On the Treewidth of Triangulated 3-Manifolds

Authors: Huszár, Kristóf ; Spreer, Jonathan ; Wagner, Uli

Abstract | Document (627 KB) | BibTeX

On Partial Covering For Geometric Set Systems

Authors: Inamdar, Tanmay ; Varadarajan, Kasturi

Abstract | Document (536 KB) | BibTeX

Optimality of Geometric Local Search

Authors: Jartoux, Bruno ; Mustafa, Nabil H.

Abstract | Document (545 KB) | BibTeX

Odd Yao-Yao Graphs are Not Spanners

Authors: Jin, Yifei ; Li, Jian ; Zhan, Wei

Abstract | Document (1,868 KB) | BibTeX

Deletion in Abstract Voronoi Diagrams in Expected Linear Time

Authors: Junginger, Kolja ; Papadopoulou, Evanthia

Abstract | Document (1,477 KB) | BibTeX

From a (p,2)-Theorem to a Tight (p,q)-Theorem

Authors: Keller, Chaya ; Smorodinsky, Shakhar

Abstract | Document (472 KB) | BibTeX

Coloring Intersection Hypergraphs of Pseudo-Disks

Authors: Keszegh, Balázs

Abstract | Document (577 KB) | BibTeX

Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts

Authors: Klute, Fabian ; Nöllenburg, Martin

Abstract | Document (594 KB) | BibTeX

Discrete Stratified Morse Theory: A User's Guide

Authors: Knudson, Kevin ; Wang, Bei

Abstract | Document (684 KB) | BibTeX

An Optimal Algorithm to Compute the Inverse Beacon Attraction Region

Authors: Kostitsyna, Irina ; Kouhestani, Bahram ; Langerman, Stefan ; Rappaport, David

Abstract | Document (756 KB) | BibTeX

On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance

Authors: van Kreveld, Marc ; Löffler, Maarten ; Wiratma, Lionov

Abstract | Document (806 KB) | BibTeX

Graph-Based Time-Space Trade-Offs for Approximate Near Neighbors

Authors: Laarhoven, Thijs

Abstract | Document (610 KB) | BibTeX

A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon

Authors: Liu, Chih-Hung

Abstract | Document (520 KB) | BibTeX

Further Consequences of the Colorful Helly Hypothesis

Authors: Martínez-Sandoval, Leonardo ; Roldán-Pensado, Edgardo ; Rubin, Natan

Abstract | Document (533 KB) | BibTeX

Random Walks on Polytopes of Constant Corank

Authors: Milatz, Malte

Abstract | Document (619 KB) | BibTeX

Table Based Detection of Degenerate Predicates in Free Space Construction

Authors: Milenkovic, Victor ; Sacks, Elisha ; Butt, Nabeel

Abstract | Document (4,287 KB) | BibTeX

Approximate Range Queries for Clustering

Authors: Oh, Eunjin ; Ahn, Hee-Kap

Abstract | Document (461 KB) | BibTeX

Point Location in Dynamic Planar Subdivisions

Authors: Oh, Eunjin ; Ahn, Hee-Kap

Abstract | Document (475 KB) | BibTeX

Edge-Unfolding Nearly Flat Convex Caps

Authors: O'Rourke, Joseph

Abstract | Document (3,333 KB) | BibTeX

A Crossing Lemma for Multigraphs

Authors: Pach, János ; Tóth, Géza

Abstract | Document (521 KB) | BibTeX

Near-Optimal Coresets of Kernel Density Estimates

Authors: Phillips, Jeff M. ; Tai, Wai Ming

Abstract | Document (592 KB) | BibTeX

Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line

Authors: Raghvendra, Sharath

Abstract | Document (482 KB) | BibTeX

Almost All String Graphs are Intersection Graphs of Plane Convex Sets

Authors: Pach, János ; Reed, Bruce ; Yuditsky, Yelena

Abstract | Document (608 KB) | BibTeX

An Improved Bound for the Size of the Set A/A+A

Authors: Roche-Newton, Oliver

Abstract | Document (425 KB) | BibTeX

Fractal Dimension and Lower Bounds for Geometric Problems

Authors: Sidiropoulos, Anastasios ; Singhal, Kritika ; Sridhar, Vijay

Abstract | Document (614 KB) | BibTeX

The Trisection Genus of Standard Simply Connected PL 4-Manifolds

Authors: Spreer, Jonathan ; Tillmann, Stephan

Abstract | Document (1,230 KB) | BibTeX

An O(n log n)-Time Algorithm for the k-Center Problem in Trees

Authors: Wang, Haitao ; Zhang, Jingru

Abstract | Document (488 KB) | BibTeX

New Bounds for Range Closest-Pair Problems

Authors: Xue, Jie ; Li, Yuan ; Rahul, Saladi ; Janardan, Ravi

Abstract | Document (687 KB) | BibTeX

Coordinated Motion Planning: The Video (Multimedia Exposition)

Authors: Becker, Aaron T. ; Fekete, Sándor P. ; Keldenich, Phillip ; Konitzny, Matthias ; Lin, Lillian ; Scheffer, Christian

Abstract | Document (6,710 KB) | BibTeX

Geometric Realizations of the 3D Associahedron (Multimedia Exposition)

Authors: Devadoss, Satyan L. ; Johnson, Daniel D. ; Lee, Justin ; Warley, Jackson

Abstract | Document (847 KB) | BibTeX

Star Unfolding of Boxes (Multimedia Exposition)

Authors: Demas, Dani ; Devadoss, Satyan L. ; Hong, Yu Xuan

Abstract | Document (858 KB) | BibTeX

VoroCrust Illustrated: Theory and Challenges (Multimedia Exposition)

Authors: Abdelkader, Ahmed ; Bajaj, Chandrajit L. ; Ebeida, Mohamed S. ; Mahmoud, Ahmed H. ; Mitchell, Scott A. ; Owens, John D. ; Rushdi, Ahmad A.

Abstract | Document (432 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

34th International Symposium on Computational Geometry (SoCG 2018)