Below is the list of accepted papers for SoCG 2019. The information is
also available at CG Week 2019 website
(http://eecs.oregonstate.edu/socg19/accepted.html ).
We look forward to see you in Portland, Oregon for CG Week in June 2019!
Yusu Wang and Gill Barequet
on behalf of SoCG 2019 Program Committee
====================== SoCG 2019 Accepted Papers =======================
** Adrian Dumitrescu. /A Product Inequality for Extreme Distances/
** Sariel Har-Peled and Mitchell Jones. /Journey to the Center of the
Point Set/
** Xavier Goaoc, Andreas Holmsen and Cyril Nicaud. /An experimental
study of forbidden patterns in geometric permutations by combinatorial
lifting/
** Shay Moran and Amir Yehudayoff. /On weak ϵ-nets and the Radon number/
** Raphaël Tinarrage, Frederic Chazal, Marc Glisse, Hirokazu Anai,
Yuichi Ike, Hiroya Inakoshi and Yuhei Umeda. /DTM-based filtrations/
** Mozhgan Mirzaei and Andrew Suk. /On grids in point-line arrangements
in the plane/
** Janos Pach and Istvan Tomon. /On the chromatic number of disjointness
graphs of curves/
** Vladimir Braverman, Moses Charikar, William Kuszmaul, David P.
Woodruff and Lin F. Yang. /The One-Way Communication Complexity of
Dynamic Time Warping Distance/
** Diego Ihara, Neshat Mohammadi and Anastasios Sidiropoulos.
/Algorithms for metric learning via contrastive embeddings/
** Pankaj K. Agarwal, Boris Aronov, Esther Ezra and Joshua Zahl. /An
Efficient Algorithm for Generalized Polynomial Partitioning and Its
Applications/
** Haitao Wang. /A Divide-and-Conquer Algorithm for Two-Point L_1
Shortest Path Queries in Polygonal Domains/
** Akanksha Agrawal, Grzegorz Guspiel, Jayakrishnan Madathil, Saket
Saurabh and Meirav Zehavi. /Connecting the Dots (with Minimum Crossings)/
** Sándor Fekete, Phillip Keldenich and Christian Scheffer. /Packing
Disks into Disks with Optimal Worst-Case Density/
** Dominique Attali, Andre Lieutier and David Salinas. /When convexity
helps collapsing complexes/
** Luis Barba. /Optimal algorithm for geodesic farthest-point Voronoi
diagrams/
** Vida Dujmovic and Pat Morin. /Dual Circumference and Collinear Sets/
** Timothy M. Chan and Sariel Har-Peled. /Smallest k-Enclosing Rectangle
Revisited/
** Chen Ziv and Micha Sharir. /On the Complexity of the k-Level in
Arrangements of Pseudoplanes/
** Yufei Tao and Yu Wang. /Distribution-Sensitive Bounds on Relative
Approximations of Geometric Ranges/
** Sergio Cabello and Timothy M. Chan. /Computing Shapley values in the
plane/
** Jean-Lou de Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim
Ophelders, Claire Pennarun, Csaba D. Tóth and Sander Verdonschot.
/Convex Polygons in Cartesian Products/
** Dror Aiger, Haim Kaplan, Efi Kokiopoulou, Micha Sharir and Bernhard
Zeisl. /General techniques for approximate incidences and their
application to the camera posing problem/
** Arnaud de Mesmay, Yo'Av Rieck, Martin Tancer and Eric Sedgwick. /The
Unbearable Hardness of Unknotting/
** Jacob Fox, Janos Pach and Andrew Suk. /Semi-algebraic colorings of
complete graphs/
** Kevin Buchin, Sariel Har-Peled and Dániel Oláh. /A Spanner for the
Day After/
** Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx and Arnaud
de Mesmay. /Almost tight lower bounds for hard cutting problems in
embedded graphs/
** Drago Bokal, Zdenek Dvorak, Petr Hlineny, Jesus Leanos, Bojan Mohar
and Tilo Wiedera. /Bounded maximum degree conjecture holds precisely for
c-crossing-critical graphs with c ≤ 12/
** Karl Bringmann, Marvin Künnemann and André Nusser. /Walking the Dog
Fast in Practice: //Algorithm Engineering of the Fréchet Distance/
** Karl Bringmann and Bhaskar Ray Chaudhury. /Polyline Simplification
has Cubic Complexity/
** Anne Driemel, Jeff Phillips and Ioannis Psarros. /On the VC dimension
of metric balls under Fr'echet and Hausdorff distances/
** Carla Binucci, Giordano Da Lozzo, Emilio Di Giacomo, Walter Didimo,
Tamara Mchedlidze and Maurizio Patrignani. /Upward Book Embeddings of
st-Graphs/
** Ching-Hsiang Hsu, Yi-Jen Chiang and Chee Yap. /Rods and Rings: Soft
Subdivision Planner for R^3 x S^2/
** David Eppstein. /Cubic Planar Graphs That Cannot Be Drawn On Few Lines/
** David Eppstein. /Counting Polygon Triangulations is Hard/
** Haitao Wang and Jie Xue. /Near-optimal Algorithms for Shortest Paths
in Weighted Unit-Disk Graphs/
** Andrey Boris Khesin, Aleksandar Nikolov and Dmitry Paramonov.
/Preconditioning for the Geometric Transportation Problem/
** Timothy M. Chan. /Dynamic Geometric Data Structures via Shallow Cuttings/
** Radoslav Fulek and Jan Kynčl. /Z_2-genus of graphs and minimum rank
of partial symmetric matrices/
** Jie Xue, Yuan Li, Saladi Rahul and Ravi Janardan. /Searching for the
closest-pair in a query translate/
** Benjamin Niedermann, Ignaz Rutter and Matthias Wolf. /Efficient
Algorithms for Ortho-Radial Graph Drawing/
** Pankaj K. Agarwal, Hsien-Chih Chang and Allen Xiao. /Geometric
Partial Matching and Unbalanced Transportation/
** Kristóf Huszár and Jonathan Spreer./ 3-Manifold triangulations of
small treewidth/
** Patrick Schnider. /Ham-Sandwich cuts and center transversals in
subspaces/
** Amer Krivosija and Alexander Munteanu. /Probabilistic smallest
enclosing ball in high dimensions via subgradient sampling/
** Michael Kerber, Michael Lesnick and Steve Oudot. /Exact computation
of the matching distance on 2-parameter persistence modules/
** Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr and Uli
Wagner. /The Crossing Tverberg Theorem/
** Siddharth Pritam and Jean-Daniel Boissonnat. /Computing Persistent
Homology of Flag Complexes via Strong Collapses/
** Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da
Lozzo and Vincenzo Roselli. /Morphing Contact Representations of Graphs/
** Ravid Cohen, Dan Halperin, Pankaj K. Agarwal and Wolfgang Mulzer.
/Maintaining the Union of Unit Discs under Insertions with Near-Optimal
Overhead/
** Hsien-Chih Chang, Marcos Cossarini and Jeff Erickson. /Lower Bounds
for Electrical Reduction on Surfaces/
** Peyman Afshani. /A New Lower Bound for Semigroup Orthogonal Range
Searching/
** Jeff Erickson and Yipu Wang. /Topologically Trivial Closed Walks in
Directed Surface Graphs/
** Peyman Afshani and Jeff Phillips. /Independent Range Sampling,
Revisited Again/
** Ulderico Fugacci and Michael Kerber. /Chunk Reduction for
Multi-Parameter Persistent Homology/
** Nathaniel Lahn and Sharath Raghvendra. /A Weighted Approach to
Maximum Cardinality Bipartite Matching Problem with Applications in
Geometric Settings/
** Ian Munro and Yakov Nekrich. /Dynamic Planar Point Location in
External Memory/
** Herbert Edelsbrunner, Žiga Virk and Hubert Wagner. /Topological Data
Analysis in Information Space/
** Hugo Akitaya, Matias Korman, Mikhail Rudoy, Diane Souvaine and Csaba
Toth. /Circumscribing Polygons and Polygonizations for Disjoint Line
Segments/
** Ivor Hoog V.D., Irina Kostitsyna, Bettina Speckmann and Maarten
Löffler. /Preprocessing Ambiguous Imprecise Points/
** Mathieu Carrière and Ulrich Bauer. /On the Metric Distortion of
Embedding Persistence Diagrams into separable Hilbert spaces/
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
