Portal - SoCG 2021

SoCG 2021	June 7-11, 2021, Buffalo, NY, USA (Virtual Conference)
37th International Symposium on Computational Geometry (SoCG 2021) Kevin Buchin and Éric Colin de Verdière (Eds.)
ISBN 978-3-95977-184-9, LIPICS Vol. 189	ISSN 1868-8969

Additional Information

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

Authors

Boissonnat, Jean-Daniel

Colin de Verdière, Éric

Cultrera di Montesano, Sebastiano

da Fonseca, Guilherme D.

Edelsbrunner, Herbert

Fisikopoulos, Vissarion

Gonzalez-Lorenzo, Aldo

Goodarzi, Afshin

Graham, Matthew

Grandoni, Fabrizio

Gurunathan, Vijaykrishna

Hendrickson, Dylan H.

Knudsen, Jakob Bæk Tejs

Makarychev, Konstantin

Pelsmajer, Michael J.

Perles, Micha A.

Pór, Attila

Ramírez-Romero, Diego

Rasmussen, Peter Michael Reichstein

Shewchuk, Jonathan Richard

Shun, Julian

Smith, Philip

Solomon, Noam

Spalding-Jamieson, Jack

Vassilevska Williams, Virginia

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Buchin, Kevin ; Colin de Verdière, Éric

Abstract | Document (560 KB) | BibTeX

On Laplacians (Invited Talk)

Authors: Ghrist, Robert

Abstract | Document (280 KB) | BibTeX

3SUM and Related Problems in Fine-Grained Complexity (Invited Talk)

Authors: Vassilevska Williams, Virginia

Abstract | Document (380 KB) | BibTeX

Classifying Convex Bodies by Their Contact and Intersection Graphs

Authors: Aamand, Anders ; Abrahamsen, Mikkel ; Knudsen, Jakob Bæk Tejs ; Rasmussen, Peter Michael Reichstein

Abstract | Document (1,261 KB) | BibTeX

Approximate Nearest-Neighbor Search for Line Segments

Authors: Abdelkader, Ahmed ; Mount, David M.

Abstract | Document (777 KB) | BibTeX

Chasing Puppies: Mobile Beacon Routing on Closed Curves

Authors: Abrahamsen, Mikkel ; Erickson, Jeff ; Kostitsyna, Irina ; Löffler, Maarten ; Miltzow, Tillmann ; Urhausen, Jérôme ; Vermeulen, Jordi ; Viglietta, Giovanni

Abstract | Document (3,155 KB) | BibTeX

Online Packing to Minimize Area or Perimeter

Authors: Abrahamsen, Mikkel ; Beretta, Lorenzo

Abstract | Document (1,029 KB) | BibTeX

Complexity of Maximum Cut on Interval Graphs

Authors: Adhikary, Ranendu ; Bose, Kaustav ; Mukherjee, Satwik ; Roy, Bodhayan

Abstract | Document (705 KB) | BibTeX

Lower Bounds for Semialgebraic Range Searching and Stabbing Problems

Authors: Afshani, Peyman ; Cheng, Pingan

Abstract | Document (957 KB) | BibTeX

Rectilinear Steiner Trees in Narrow Strips

Authors: Alkema, Henk ; de Berg, Mark

Abstract | Document (962 KB) | BibTeX

Characterizing Universal Reconfigurability of Modular Pivoting Robots

Authors: A. Akitaya, Hugo ; Demaine, Erik D. ; Gonczi, Andrei ; Hendrickson, Dylan H. ; Hesterberg, Adam ; Korman, Matias ; Korten, Oliver ; Lynch, Jayson ; Parada, Irene ; Sacristán, Vera

Abstract | Document (1,469 KB) | BibTeX

Adjacency Graphs of Polyhedral Surfaces

Authors: Arseneva, Elena ; Kleist, Linda ; Klemz, Boris ; Löffler, Maarten ; Schulz, André ; Vogtenhuber, Birgit ; Wolff, Alexander

Abstract | Document (2,935 KB) | BibTeX

On Undecided LP, Clustering and Active Learning

Authors: Ashur, Stav ; Har-Peled, Sariel

Abstract | Document (963 KB) | BibTeX

Two-Sided Kirszbraun Theorem

Authors: Backurs, Arturs ; Mahabadi, Sepideh ; Makarychev, Konstantin ; Makarychev, Yury

Abstract | Document (731 KB) | BibTeX

Orientation Preserving Maps of the Square Grid

Authors: Bárány, Imre ; Pór, Attila ; Valtr, Pavel

Abstract | Document (917 KB) | BibTeX

Light Euclidean Steiner Spanners in the Plane

Authors: Bhore, Sujoy ; Tóth, Csaba D.

Abstract | Document (1,058 KB) | BibTeX

Counting Cells of Order-k Voronoi Tessellations in ℝ³ with Morse Theory

Authors: Biswas, Ranita ; Cultrera di Montesano, Sebastiano ; Edelsbrunner, Herbert ; Saghafian, Morteza

Abstract | Document (711 KB) | BibTeX

Tracing Isomanifolds in ℝ^d in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations

Authors: Boissonnat, Jean-Daniel ; Kachanovich, Siargey ; Wintraecken, Mathijs

Abstract | Document (1,927 KB) | BibTeX

Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation

Authors: Bringmann, Karl ; Nusser, André

Abstract | Document (917 KB) | BibTeX

Optimal Bounds for the Colorful Fractional Helly Theorem

Authors: Bulavka, Denys ; Goodarzi, Afshin ; Tancer, Martin

Abstract | Document (828 KB) | BibTeX

An Integer Programming Formulation Using Convex Polygons for the Convex Partition Problem

Authors: Cambazard, Hadrien ; Catusse, Nicolas

Abstract | Document (704 KB) | BibTeX

Geometric Algorithms for Sampling the Flux Space of Metabolic Networks

Authors: Chalkis, Apostolos ; Fisikopoulos, Vissarion ; Tsigaridas, Elias ; Zafeiropoulos, Haris

Abstract | Document (2,243 KB) | BibTeX

A Family of Metrics from the Truncated Smoothing of Reeb Graphs

Authors: Chambers, Erin Wolf ; Munch, Elizabeth ; Ophelders, Tim

Abstract | Document (1,105 KB) | BibTeX

Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries

Authors: Chambers, Erin Wolf ; Lazarus, Francis ; de Mesmay, Arnaud ; Parsa, Salman

Abstract | Document (772 KB) | BibTeX

Faster Algorithms for Largest Empty Rectangles and Boxes

Authors: Chan, Timothy M.

Abstract | Document (769 KB) | BibTeX

More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time

Authors: Chan, Timothy M. ; He, Qizheng

Abstract | Document (749 KB) | BibTeX

Approximating the (Continuous) Fréchet Distance

Authors: Colombe, Connor ; Fox, Kyle

Abstract | Document (817 KB) | BibTeX

Computing the Multicover Bifiltration

Authors: Corbet, René ; Kerber, Michael ; Lesnick, Michael ; Osang, Georg

Abstract | Document (1,336 KB) | BibTeX

Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and Their Applications

Authors: Csikós, Mónika ; Mustafa, Nabil H.

Abstract | Document (1,947 KB) | BibTeX

Colouring Polygon Visibility Graphs and Their Generalizations

Authors: Davies, James ; Krawczyk, Tomasz ; McCarty, Rose ; Walczak, Bartosz

Abstract | Document (673 KB) | BibTeX

Computing Zigzag Persistence on Graphs in Near-Linear Time

Authors: Dey, Tamal K. ; Hou, Tao

Abstract | Document (780 KB) | BibTeX

Minimal Delaunay Triangulations of Hyperbolic Surfaces

Authors: Ebbens, Matthijs ; Parlier, Hugo ; Vegter, Gert

Abstract | Document (916 KB) | BibTeX

The Density Fingerprint of a Periodic Point Set

Authors: Edelsbrunner, Herbert ; Heiss, Teresa ; Kurlin, Vitaliy ; Smith, Philip ; Wintraecken, Mathijs

Abstract | Document (3,153 KB) | BibTeX

On the Edge Crossings of the Greedy Spanner

Authors: Eppstein, David ; Khodabandeh, Hadi

Abstract | Document (770 KB) | BibTeX

On Ray Shooting for Triangles in 3-Space and Related Problems

Authors: Ezra, Esther ; Sharir, Micha

Abstract | Document (780 KB) | BibTeX

On Rich Lenses in Planar Arrangements of Circles and Related Problems

Authors: Ezra, Esther ; Raz, Orit E. ; Sharir, Micha ; Zahl, Joshua

Abstract | Document (747 KB) | BibTeX

Packing Squares into a Disk with Optimal Worst-Case Density

Authors: Fekete, Sándor P. ; Gurunathan, Vijaykrishna ; Juneja, Kushagra ; Keldenich, Phillip ; Kleist, Linda ; Scheffer, Christian

Abstract | Document (1,663 KB) | BibTeX

Sunflowers in Set Systems of Bounded Dimension

Authors: Fox, Jacob ; Pach, János ; Suk, Andrew

Abstract | Document (611 KB) | BibTeX

Strong Hanani-Tutte for the Torus

Authors: Fulek, Radoslav ; Pelsmajer, Michael J. ; Schaefer, Marcus

Abstract | Document (870 KB) | BibTeX

Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More

Authors: Gálvez, Waldo ; Grandoni, Fabrizio ; Khan, Arindam ; Ramírez-Romero, Diego ; Wiese, Andreas

Abstract | Document (839 KB) | BibTeX

A Stepping-Up Lemma for Topological Set Systems

Authors: Goaoc, Xavier ; Holmsen, Andreas F. ; Patáková, Zuzana

Abstract | Document (754 KB) | BibTeX

Throwing a Sofa Through the Window

Authors: Halperin, Dan ; Sharir, Micha ; Yehuda, Itay

Abstract | Document (1,475 KB) | BibTeX

Stabbing Convex Bodies with Lines and Flats

Authors: Har-Peled, Sariel ; Jones, Mitchell

Abstract | Document (912 KB) | BibTeX

Reliable Spanners for Metric Spaces

Authors: Har-Peled, Sariel ; Mendel, Manor ; Oláh, Dániel

Abstract | Document (800 KB) | BibTeX

A Practical Algorithm with Performance Guarantees for the Art Gallery Problem

Authors: Hengeveld, Simon B. ; Miltzow, Tillmann

Abstract | Document (1,171 KB) | BibTeX

Approximate Range Counting Under Differential Privacy

Authors: Huang, Ziyue ; Yi, Ke

Abstract | Document (770 KB) | BibTeX

Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs

Authors: Karczmarz, Adam ; Pawlewicz, Jakub ; Sankowski, Piotr

Abstract | Document (727 KB) | BibTeX

No Krasnoselskii Number for General Sets

Authors: Keller, Chaya ; Perles, Micha A.

Abstract | Document (716 KB) | BibTeX

On Guillotine Separable Packings for the Two-Dimensional Geometric Knapsack Problem

Authors: Khan, Arindam ; Maiti, Arnab ; Sharma, Amatya ; Wiese, Andreas

Abstract | Document (758 KB) | BibTeX

Restricted Constrained Delaunay Triangulations

Authors: Khoury, Marc ; Shewchuk, Jonathan Richard

Abstract | Document (1,051 KB) | BibTeX

Near Neighbor Search via Efficient Average Distortion Embeddings

Authors: Kush, Deepanshu ; Nikolov, Aleksandar ; Tang, Haohua

Abstract | Document (655 KB) | BibTeX

Convergence of Gibbs Sampling: Coordinate Hit-And-Run Mixes Fast

Authors: Laddha, Aditi ; Vempala, Santosh S.

Abstract | Document (813 KB) | BibTeX

Combinatorial Resultants in the Algebraic Rigidity Matroid

Authors: Malić, Goran ; Streinu, Ileana

Abstract | Document (893 KB) | BibTeX

Parameterized Complexity of Quantum Knot Invariants

Authors: Maria, Clément

Abstract | Document (1,726 KB) | BibTeX

Efficient Generation of Rectangulations via Permutation Languages

Authors: Merino, Arturo ; Mütze, Torsten

Abstract | Document (1,220 KB) | BibTeX

Polygon-Universal Graphs

Authors: Ophelders, Tim ; Rutter, Ignaz ; Speckmann, Bettina ; Verbeek, Kevin

Abstract | Document (954 KB) | BibTeX

On Rich Points and Incidences with Restricted Sets of Lines in 3-Space

Authors: Sharir, Micha ; Solomon, Noam

Abstract | Document (739 KB) | BibTeX

Sketching Persistence Diagrams

Authors: Sheehy, Donald R. ; Sheth, Siddharth

Abstract | Document (805 KB) | BibTeX

A Sparse Delaunay Filtration

Authors: Sheehy, Donald R.

Abstract | Document (1,446 KB) | BibTeX

An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons

Authors: Wang, Haitao

Abstract | Document (931 KB) | BibTeX

A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem

Authors: Wang, Yiqiu ; Yu, Shangdi ; Gu, Yan ; Shun, Julian

Abstract | Document (1,012 KB) | BibTeX

An Interactive Tool for Experimenting with Bounded-Degree Plane Geometric Spanners (Media Exposition)

Authors: Anderson, Fred ; Ghosh, Anirban ; Graham, Matthew ; Mougeot, Lucas ; Wisnosky, David

Abstract | Document (636 KB) | BibTeX

Can You Walk This? Eulerian Tours and IDEA Instructions (Media Exposition)

Authors: Becker, Aaron T. ; Fekete, Sándor P. ; Konitzny, Matthias ; Morr, Sebastian ; Schmidt, Arne

Abstract | Document (2,125 KB) | BibTeX

Shadoks Approach to Low-Makespan Coordinated Motion Planning (CG Challenge)

Authors: Crombez, Loïc ; da Fonseca, Guilherme D. ; Gerard, Yan ; Gonzalez-Lorenzo, Aldo ; Lafourcade, Pascal ; Libralesso, Luc

Abstract | Document (1,011 KB) | BibTeX

Coordinated Motion Planning Through Randomized k-Opt (CG Challenge)

Authors: Liu, Paul ; Spalding-Jamieson, Jack ; Zhang, Brandon ; Zheng, Da Wei

Abstract | Document (907 KB) | BibTeX

A Simulated Annealing Approach to Coordinated Motion Planning (CG Challenge)

Authors: Yang, Hyeyun ; Vigneron, Antoine

Abstract | Document (694 KB) | BibTeX

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

37th International Symposium on Computational Geometry (SoCG 2021)