


default search action
34th SoCG 2018: Budapest, Hungary
- Bettina Speckmann, Csaba D. Tóth:
34th International Symposium on Computational Geometry, SoCG 2018, June 11-14, 2018, Budapest, Hungary. LIPIcs 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018, ISBN 978-3-95977-066-8 - Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks. 0:i-0:xi
- Ahmed Abdelkader, Chandrajit L. Bajaj
, Mohamed S. Ebeida, Ahmed H. Mahmoud, Scott A. Mitchell, John D. Owens, Ahmad A. Rushdi
:
Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm. 1:1-1:16 - A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin
, Michiel H. M. Smid, Shakhar Smorodinsky
:
Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs. 2:1-2:12 - Michal Adamaszek, Henry Adams, Ellen Gasparovic, Maria Gommel, Emilie Purvine, Radmila Sazdanovic
, Bei Wang
, Yusu Wang, Lori Ziegelmeier:
Vietoris-Rips and Cech Complexes of Metric Gluings. 3:1-3:15 - Pankaj K. Agarwal, Lars Arge, Frank Staals:
Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon. 4:1-4:14 - Ryo Ashida, Kotaro Nakagawa:
O~(n^{1/3})-Space Algorithm for the Grid Graph Reachability Problem. 5:1-5:13 - Sang Won Bae
, Sergio Cabello, Otfried Cheong, Yoonsung Choi, Fabian Stehn, Sang Duk Yoon:
The Reverse Kakeya Problem. 6:1-6:13 - Sayan Bandyapadhyay, Santanu Bhowmick, Tanmay Inamdar
, Kasturi R. Varadarajan:
Capacitated Covering Problems in Geometric Spaces. 7:1-7:15 - Ahmad Biniaz, Prosenjit Bose, Paz Carmi, Anil Maheshwari, J. Ian Munro, Michiel H. M. Smid:
Faster Algorithms for some Optimization Problems on Collinear Points. 8:1-8:14 - Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, Mathijs Wintraecken
:
Local Criteria for Triangulation of Manifolds. 9:1-9:14 - Jean-Daniel Boissonnat, André Lieutier, Mathijs Wintraecken
:
The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces. 10:1-10:14 - Édouard Bonnet, Panos Giannopoulos:
Orthogonal Terrain Guarding is NP-complete. 11:1-11:15 - Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski
, Florian Sikora:
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs. 12:1-12:15 - Håvard Bakke Bjerkevik
, Magnus Bakke Botnan:
Computational Complexity of the Interleaving Distance. 13:1-13:15 - Adam Brown, Bei Wang
:
Sheaf-Theoretic Stratification Learning. 14:1-14:14 - Mickaël Buchet
, Emerson G. Escolar
:
Realizations of Indecomposable Persistence Modules of Arbitrarily Large Dimension. 15:1-15:13 - Kevin Buchin
, Jeff M. Phillips, Pingfan Tang:
Approximating the Distribution of the Median and other Robust Estimators on Uncertain Data. 16:1-16:14 - Boris Bukh, Xavier Goaoc, Alfredo Hubard, Matthew Trager:
Consistent Sets of Lines with no Colorful Incidence. 17:1-17:14 - Benjamin A. Burton
:
The HOMFLY-PT Polynomial is Fixed-Parameter Tractable. 18:1-18:14 - Ludovic Calès
, Apostolos Chalkis, Ioannis Z. Emiris
, Vissarion Fisikopoulos
:
Practical Volume Computation of Structured Convex Bodies, and an Application to Modeling Portfolio Dependencies and Financial Crises. 19:1-19:15 - Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman, Aurélien Ooms:
Subquadratic Encodings for Point Configurations. 20:1-20:14 - Timothy Carpenter, Fedor V. Fomin
, Daniel Lokshtanov, Saket Saurabh, Anastasios Sidiropoulos:
Algorithms for Low-Distortion Embeddings into Arbitrary 1-Dimensional Spaces. 21:1-21:14 - Jérémie Chalopin, Victor Chepoi
, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, Yann Vaxès:
Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. 22:1-22:15 - Timothy M. Chan:
Tree Drawings Revisited. 23:1-23:15 - Timothy M. Chan, Dimitrios Skrepetos:
Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs. 24:1-24:13 - Timothy M. Chan, Konstantinos Tsakalidis:
Dynamic Planar Orthogonal Point Location in Sublogarithmic Time. 25:1-25:15 - Frédéric Chazal, Vincent Divol:
The Density of Expected Persistence Diagrams and its Kernel Based Estimation. 26:1-26:15 - Éric Colin de Verdière, Thomas Magnard, Bojan Mohar:
Embedding Graphs into Two-Dimensional Simplicial Complexes. 27:1-27:14 - Roee David, Karthik C. S.
, Bundit Laekhanukit:
On the Complexity of Closest Pair via Polar-Pair of Point-Sets. 28:1-28:15 - Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Christian Scheffer, Henk Meijer:
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch. 29:1-29:15 - Olivier Devillers, Sylvain Lazard, William J. Lenhart:
3D Snap Rounding. 30:1-30:14 - Tamal K. Dey, Jiayuan Wang, Yusu Wang:
Graph Reconstruction by Discrete Morse Theory. 31:1-31:15 - Tamal K. Dey, Cheng Xin:
Computing Bottleneck Distance for 2-D Interval Decomposable Modules. 32:1-32:15 - Zdenek Dvorák, Petr Hlinený
, Bojan Mohar:
Structure and Generation of Crossing-Critical Graphs. 33:1-33:14 - Herbert Edelsbrunner, Georg Osang:
The Multi-cover Persistence of Euclidean Balls. 34:1-34:14 - Herbert Edelsbrunner, Ziga Virk
, Hubert Wagner:
Smallest Enclosing Spheres and Chernoff Points in BregmanGeometry. 35:1-35:13 - Michael Elkin, Ofer Neiman:
Near Isometric Terminal Embeddings for Doubling Metrics. 36:1-36:15 - Ioannis Z. Emiris
, Ioannis Psarros
:
Products of Euclidean Metrics and Applications to Proximity Questions among Curves. 37:1-37:13 - Stefan Felsner, Linda Kleist
, Torsten Mütze, Leon Sering
:
Rainbow Cycles in Flip Graphs. 38:1-38:14 - Radoslav Fulek
, Jan Kyncl
:
Hanani-Tutte for Approximating Maps of Graphs. 39:1-39:15 - Radoslav Fulek
, Jan Kyncl
:
The Z_2-Genus of Kuratowski Minors. 40:1-40:14 - Xavier Goaoc, Pavel Paták, Zuzana Patáková
, Martin Tancer
, Uli Wagner:
Shellability is NP-Complete. 41:1-41:15 - Arthur van Goethem, Kevin Verbeek
:
Optimal Morphs of Planar Orthogonal Drawings. 42:1-42:14 - Joshua A. Grochow
, Jamie Tucker-Foltz:
Computational Topology and the Unique Games Conjecture. 43:1-43:16 - Andreas Haas:
Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality. 44:1-44:14 - Ivor van der Hoog
, Elena Khramtcova, Maarten Löffler:
Dynamic Smooth Compressed Quadtrees. 45:1-45:15 - Kristóf Huszár
, Jonathan Spreer
, Uli Wagner:
On the Treewidth of Triangulated 3-Manifolds. 46:1-46:15 - Tanmay Inamdar
, Kasturi R. Varadarajan:
On Partial Covering For Geometric Set Systems. 47:1-47:14 - Bruno Jartoux
, Nabil H. Mustafa
:
Optimality of Geometric Local Search. 48:1-48:15 - Yifei Jin, Jian Li, Wei Zhan:
Odd Yao-Yao Graphs are Not Spanners. 49:1-49:15 - Kolja Junginger, Evanthia Papadopoulou
:
Deletion in Abstract Voronoi Diagrams in Expected Linear Time. 50:1-50:14 - Chaya Keller
, Shakhar Smorodinsky
:
From a (p, 2)-Theorem to a Tight (p, q)-Theorem. 51:1-51:14 - Balázs Keszegh:
Coloring Intersection Hypergraphs of Pseudo-Disks. 52:1-52:15 - Fabian Klute
, Martin Nöllenburg:
Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts. 53:1-53:14 - Kevin P. Knudson
, Bei Wang
:
Discrete Stratified Morse Theory: A User's Guide. 54:1-54:14 - Irina Kostitsyna
, Bahram Kouhestani, Stefan Langerman, David Rappaport:
An Optimal Algorithm to Compute the Inverse Beacon Attraction Region. 55:1-55:14 - Marc J. van Kreveld
, Maarten Löffler, Lionov Wiratma:
On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance. 56:1-56:14 - Thijs Laarhoven:
Graph-Based Time-Space Trade-Offs for Approximate Near Neighbors. 57:1-57:14 - Chih-Hung Liu:
A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon. 58:1-58:14 - Leonardo Martínez-Sandoval
, Edgardo Roldán-Pensado
, Natan Rubin
:
Further Consequences of the Colorful Helly Hypothesis. 59:1-59:14 - Malte Milatz:
Random Walks on Polytopes of Constant Corank. 60:1-60:14 - Victor Milenkovic, Elisha Sacks, Nabeel Butt:
Table Based Detection of Degenerate Predicates in Free Space Construction. 61:1-61:14 - Eunjin Oh, Hee-Kap Ahn
:
Approximate Range Queries for Clustering. 62:1-62:14 - Eunjin Oh, Hee-Kap Ahn
:
Point Location in Dynamic Planar Subdivisions. 63:1-63:14 - Joseph O'Rourke:
Edge-Unfolding Nearly Flat Convex Caps. 64:1-64:14 - János Pach, Géza Tóth:
A Crossing Lemma for Multigraphs. 65:1-65:13 - Jeff M. Phillips, Wai Ming Tai:
Near-Optimal Coresets of Kernel Density Estimates. 66:1-66:13 - Sharath Raghvendra:
Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line. 67:1-67:14 - János Pach, Bruce A. Reed, Yelena Yuditsky:
Almost All String Graphs are Intersection Graphs of Plane Convex Sets. 68:1-68:14 - Oliver Roche-Newton
:
An Improved Bound for the Size of the Set A/A+A. 69:1-69:12 - Anastasios Sidiropoulos, Kritika Singhal, Vijay Sridhar
:
Fractal Dimension and Lower Bounds for Geometric Problems. 70:1-70:14 - Jonathan Spreer
, Stephan Tillmann
:
The Trisection Genus of Standard Simply Connected PL 4-Manifolds. 71:1-71:13 - Haitao Wang, Jingru Zhang:
An O(n log n)-Time Algorithm for the k-Center Problem in Trees. 72:1-72:15 - Jie Xue
, Yuan Li, Saladi Rahul, Ravi Janardan:
New Bounds for Range Closest-Pair Problems. 73:1-73:14 - Aaron T. Becker
, Sándor P. Fekete, Phillip Keldenich, Matthias Konitzny, Lillian Lin, Christian Scheffer:
Coordinated Motion Planning: The Video (Multimedia Exposition). 74:1-74:6 - Satyan L. Devadoss, Daniel D. Johnson, Justin Lee, Jackson Warley:
Geometric Realizations of the 3D Associahedron (Multimedia Exposition). 75:1-75:4 - Dani Demas, Satyan L. Devadoss, Yu Xuan Hong:
Star Unfolding of Boxes (Multimedia Exposition). 76:1-76:4 - Ahmed Abdelkader, Chandrajit L. Bajaj, Mohamed S. Ebeida, Ahmed H. Mahmoud, Scott A. Mitchell, John D. Owens, Ahmad A. Rushdi:
VoroCrust Illustrated: Theory and Challenges (Multimedia Exposition). 77:1-77:4

manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.