35th International Symposium on Computational Geometry (SoCG 2019)

p000-Frontmatter......Page 1
 Foreword......Page 11
 Conference Organization......Page 13
 Additional Reviewers......Page 15
p001-Dasgupta......Page 17
p002-Donald......Page 19
 Introduction......Page 21
  The Previous Results......Page 22
 Preliminaries......Page 23
  Definitions and Set up......Page 24
  The Main Lemma......Page 26
   Notation and Setup......Page 28
  The Lower Bound Proof......Page 32
 The Upper Bounds......Page 33
 Conclusions......Page 34
 Introduction......Page 35
 A Randomized Data Structure......Page 37
  Preliminaries......Page 39
  A Solution with Expected Query Time......Page 40
   Generating Candidate Points......Page 41
   Constructing the k Samples......Page 42
 Lower Bound for Worst-Case Time with Exact Weights......Page 44
p005-Agarwal......Page 49
 Introduction......Page 50
  Polynomials, partitioning, and quantifier elimination......Page 51
  Range spaces, VC dimension, and epsilon-samples......Page 53
  The parameter space of semi-algebraic sets......Page 54
  A singly-exponential algorithm......Page 55
  Speeding up the algorithm using epsilon-sampling......Page 56
  Point-enclosure queries......Page 57
  Range searching......Page 58
  Vertical ray shooting......Page 59
  Cutting algebraic curves into pseudo-segments......Page 61
 Introduction......Page 63
 Minimum-cost partial matchings using Hungarian algorithm......Page 66
  From matching to circulation......Page 67
  A cost-scaling algorithm......Page 68
  Fast implementation of refinement stage......Page 71
  An efficient implementation......Page 73
p007-Agrawal......Page 77
 Introduction......Page 78
  Our Contribution......Page 79
  Related Works......Page 82
 NP-hardness for CM-PM......Page 84
 FPT Algorithm for CM-PM......Page 85
p008-Aiger......Page 95
 Introduction......Page 96
 From camera positioning to approximate incidences......Page 98
  The surfaces sigma_w......Page 99
  Measuring proximity......Page 100
 Primal-dual algorithm for geometric proximity......Page 101
 Geometric proximity via canonical surfaces......Page 103
  Canonizing the input surfaces......Page 104
  Approximately counting {epsilon}-incidences......Page 105
  Error analysis......Page 106
  Experimental Results: Summary......Page 107
p009-Akitaya......Page 109
 Introduction......Page 110
 Large Subsets with Circumscribing Polygons......Page 111
 Disjoint Segments versus Disjoint Rays......Page 118
 Hardness for Circumscribing Polygons......Page 120
 Simple Polygonizations of Disjoint Segments......Page 121
  Higher Dimensions......Page 122
  Open Problems......Page 123
p010-Angelini......Page 127
 Introduction......Page 128
 Definitions and Preliminaries......Page 130
  From RT-Representations to Schnyder Woods......Page 131
  From Schnyder Woods to RT-Representations......Page 132
 Geometric Tools......Page 133
  Moving a Triangle Along a Diagonal......Page 135
  A Flipping Algorithm......Page 136
  Morphing Representations with the same Schnyder Wood......Page 137
 A Decision Algorithm......Page 139
 Conclusions and Open Problems......Page 140
 Introduction......Page 143
  Euclidean space, distances and convex sets......Page 144
  Filtrations......Page 145
  Statement of results......Page 146
  Building a filtration......Page 147
  Perturbing filtrations......Page 148
  Studying events in the filtration......Page 150
 Collapsing Rips complexes......Page 153
  Two geometric lemmas......Page 155
 Future work......Page 157
 Introduction......Page 159
 Preliminaries......Page 162
  The simplification transformation......Page 163
  A smaller polygon......Page 165
  Preprocessing the red sites......Page 167
 Inserting back the red sites......Page 168
  The insertion process......Page 169
  Algorithmic description......Page 170
p013-Binucci......Page 173
 Introduction......Page 174
 Preliminaries......Page 175
 NP-Completeness for kUBE (k >= 3)......Page 176
 Existential Results for 2UBE......Page 181
 Testing 2UBE for Plane Graphs with Special Faces......Page 182
 Testing Algorithms for 2UBE Parameterized by the Branchwidth......Page 183
 Conclusion and Open Problems......Page 190
p014-Bokal......Page 195
 Introduction......Page 196
 Graphs and the crossing number......Page 198
 Crossing-critical graphs with at most 12 crossings......Page 199
 Explicit 13-crossing-critical graphs with large degree......Page 202
 Extended crossing-critical constructions......Page 206
 Concluding remarks and open problems......Page 207
 Introduction......Page 211
  Our results and methods......Page 213
  Graph construction......Page 214
  Preserving Euclidean distance......Page 216
  Generalized preconditioning framework......Page 217
  Preconditioner construction......Page 219
 Generating a transportation map......Page 222
p016-Braverman......Page 225
 Introduction......Page 226
 Preliminaries......Page 227
 Technical overview......Page 229
 The bounded -DTW problem......Page 235
 Introduction......Page 241
  Preprocessing......Page 244
  Free-space diagram......Page 245
  Pruning rules......Page 246
  Implementation details of simple boundaries......Page 249
  Effects of combined pruning rules......Page 250
 Decider with filters......Page 251
  Decider setting......Page 252
  Query setting......Page 254
 Introduction......Page 263
  Contribution 2: Conditional lower bound......Page 264
 Preliminaries......Page 266
 Algorithms for Global-Fréchet simplification......Page 267
  An O(kn^5) algorithm for Global Fréchet simplification......Page 268
  An O(n^3) algorithm for Global-Fréchet simplification......Page 269
   Cell Reachability......Page 271
 Conditional lower bound for curve simplification......Page 272
  Overview of the reduction......Page 273
  Cordinate gadgets......Page 274
   The vectors a\', b\', c\', and s\'......Page 276
   The vectors a\'\',b\'\', c\'\', and s\'\'......Page 277
 Introduction......Page 279
  Our results......Page 281
  Expanders are reliable......Page 282
  Bounding the size of the shadow......Page 283
   Analysis......Page 284
  Construction of theta-reliable exact spanners in one dimension......Page 287
  Analysis......Page 288
  Analysis......Page 290
 Conclusions......Page 292
 Introduction......Page 295
 Preliminaries......Page 299
 Convex hull......Page 300
  Notation for axis-parallel problems......Page 302
  Interpreting Shapley values geometrically......Page 304
  Handling empty blocks......Page 305
  Chains......Page 306
  General point sets......Page 308
  Area of the bounding box......Page 309
 Conclusions......Page 310
 Introduction......Page 315
  Persistence Diagrams......Page 317
  Bi-Lipschitz embeddings.......Page 319
 Mapping into separable Hilbert spaces......Page 320
 Mapping into finite-dimensional Hilbert spaces......Page 324
 Experiments......Page 325
 Conclusion......Page 327
p022-DeCarufel......Page 331
 Introduction......Page 332
  Upper bounds in the plane......Page 334
  Upper bounds in higher dimensions......Page 336
  Lower bounds in higher dimensions......Page 338
  Convex caps......Page 341
  Upper bounds......Page 343
  Lower bounds......Page 344
  The maximum number of weakly convex polygons......Page 345
 Introduction......Page 349
  An exact near-quadratic algorithm......Page 351
  k-sensitive running time for smallest area......Page 353
  An approximation algorithm for smallest area......Page 355
  3-sided smallest k-enclosing rectangle......Page 358
  Arbitrarily oriented smallest k-enclosing rectangle......Page 359
  Subset sum for k-enclosing rectangle......Page 360
  Conditional lower bounds......Page 361
 Introduction......Page 365
 Dynamic 3D Convex Hull Size......Page 368
 Dynamic 2D Hausdorff Distance......Page 371
 Dynamic 3D Convex Hull Queries......Page 373
 Dynamic 2D Bichromatic Closest Pair......Page 375
 Introduction......Page 379
  Multicurves and medial graphs......Page 381
  Local moves......Page 382
  Equivalence of tightness......Page 383
 Two-terminal plane graphs......Page 385
  Smoothing lemma in the annulus......Page 386
  Quadratic lower bound......Page 387
  Defect......Page 388
  Tangle flips......Page 389
  Back to planar electrical moves......Page 391
 Open problems......Page 392
p026-Agarwal......Page 395
 Introduction......Page 396
  Data structure and operations......Page 397
  Finding the intersection point of two lower envelopes......Page 398
 Maintaining the union of unit discs under insertions......Page 402
  Preliminaries......Page 403
   Dynamically maintaining the upper curves......Page 405
 Intersection-searching of unit arcs with unit disc......Page 407
p027-Cohen-Addad......Page 411
 Introduction......Page 412
 Preliminaries......Page 415
 The 4-regular graph tiling problem......Page 417
 Multiway cut with four terminals......Page 420
 Shortest cut graph......Page 422
 Multiway cut with a large number of terminals......Page 423
p028-Driemel......Page 427
  Distance measures......Page 428
  Range spaces......Page 429
  Range spaces induced by distance measures......Page 430
 Our Approach......Page 431
 Basic Idea: Discrete Fréchet and Hausdorff......Page 432
  Geometric primitives......Page 433
  Bounding the VC-Dimension......Page 434
  Fréchet distance predicates......Page 435
  Fréchet distance VC dimension bounds......Page 436
 Lower bounds......Page 438
 Implications......Page 439
 Introduction......Page 443
 Proof of Theorem 1......Page 445
  Faces that are Touched, Pinched, and Caressed......Page 446
  Auxilliary Graphs and Trees: H, H, T_0, and T_1......Page 448
  Interactions Between Bad Nodes......Page 452
  Really Bad Nodes......Page 453
  Tree/Cycle Surgery......Page 454
 Discussion......Page 457
 Introduction......Page 461
 Setup of the proof......Page 462
 Charging scheme......Page 463
 Charging scheme analysis......Page 467
 Conclusion of the proof......Page 472
 Introduction......Page 473
 Entropy and Relative Entropy......Page 475
 Fisher Information Metric......Page 477
 Information and Loss......Page 479
 TDA in Information Space......Page 481
 Discussion......Page 485
 Introduction......Page 487
  Overview......Page 490
  Nested polygons with no surrounded crossings......Page 491
  The main result......Page 493
 Series-parallel graphs......Page 494
  Apex-tree graphs requiring many lines......Page 496
  Drawing apex-tree graphs on few lines......Page 498
 Conclusions and open problems......Page 499
 Introduction......Page 503
  Counting complexity......Page 504
 Red–blue arrangements......Page 505
 Reduction to triangulation......Page 507
  From segments to polygons......Page 508
  Triangulation within a gadget......Page 509
  Counting within a gadget......Page 510
  Global counting......Page 513
  Completing the reduction......Page 515
 Conclusions and open problems......Page 516
 Introduction......Page 521
 Background......Page 523
  Simple Cycles......Page 525
  Non-simple Closed Walks......Page 526
 Bounding Closed Walks......Page 528
  Edge Labeling......Page 530
  Hyperbolic Geometry......Page 531
  Triangulation......Page 532
  Context-Free Grammar......Page 534
 Introduction......Page 539
 Preliminaries......Page 541
  Boundary Packing: A Subroutine......Page 542
  Ring Packing: A Subroutine......Page 543
  Analysis of Phase 1 - The Recursion......Page 544
  Outline of the Remaining Analysis......Page 545
  Analysis of Boundary Packing......Page 546
  Analysis of Ring Packing......Page 547
  Analysis of the Algorithm for the Case r_1 <= 0.495......Page 553
 Hardness......Page 554
 Conclusions......Page 555
 Introduction......Page 559
 Multicolor Ramsey numbers for small cliques – Proof of Theorem 1......Page 562
 Multicolor semi-algebraic regularity lemma – Proof of Theorem 2......Page 565
 Generalized Ramsey numbers for semi-algebraic colorings – Proof of Theorem 3......Page 567
 Concluding remarks......Page 569
 Introduction......Page 571
 Background......Page 573
 Algorithm......Page 576
 Correctness......Page 577
 Optimality and complexity......Page 580
 Implementation and experimental results......Page 582
 Conclusion......Page 583
p038-Fulek......Page 585
 Introduction and Results......Page 586
 Proof of Lemma 7......Page 589
  Geometric proof of the parity Lemma 9 for d=2......Page 590
  Combinatorial proof of the parity Lemma 9......Page 591
  A Topological version of Theorem 3......Page 593
  Stronger conditions on crossings......Page 595
  Computational complexity of finding a crossing Tverberg partition......Page 596
 Introduction......Page 599
 Graphs on surfaces......Page 601
  Combinatorial representation of drawings......Page 602
  Bounding Z2-genus by matrix rank......Page 603
 Minimum rank of partial symmetric matrices......Page 605
  Block symmetric matrices......Page 606
 Estimating the Z2-genus and the Euler Z2-genus of Km,n......Page 607
 Amalgamations......Page 608
  1-amalgamations......Page 609
  2-amalgamations......Page 610
 Conclusion......Page 612
 Introduction......Page 615
  Contributions......Page 616
  Discussion and related work......Page 617
 Semi-algebraic parameterization......Page 619
 Combinatorial lifting......Page 621
  Outline......Page 624
  Description......Page 625
  Discussion......Page 626
 Experimental results......Page 627
 Geometric analysis (size two)......Page 628
 Introduction......Page 631
  Ranges spaces, VC dimension, samples and nets......Page 633
 Approximating the centerpoint via Radon\'s urn......Page 634
  Analysis......Page 635
   Back to the urn......Page 636
   Analysis......Page 637
  Lowerbounding a function with a gradient oracle......Page 639
   Correctness......Page 640
  The construction......Page 642
  The result......Page 643
p042-VanDerHoog......Page 645
 Introduction......Page 646
 Ambiguity......Page 648
  Properties of ambiguity......Page 649
  Level permutation......Page 653
  Algorithm......Page 654
 Quadtrees......Page 656
  1-dimensional quadtrees on unit-size intervals......Page 658
 Conclusion......Page 659
 Introduction......Page 661
  What is New: Contributions of This Paper......Page 664
 Literature Review......Page 665
 Subdivision Charts and Atlas for S^2......Page 666
 Approximate Footprints for Boxes in R^{3} x S^{2}......Page 667
  On Sigma_2-Sets......Page 668
 Soft Predicates for a Rod Robot......Page 669
 Soft Predicates for a Ring Robot......Page 671
 Practical Efficiency of Correct Implementations......Page 672
 Conclusions......Page 674
 Introduction......Page 679
  Triangulations and Heegaard splittings of 3-manifolds......Page 681
  Orientable Seifert fibered spaces......Page 682
  Layered triangulations......Page 683
  Treewidth versus Heegaard genus......Page 685
  An algorithmic aspect of layered triangulations......Page 686
 3-Manifolds of treewidth at most one......Page 687
 Some 3-manifolds of treewidth two......Page 691
 Introduction......Page 699
  Problem formulation......Page 700
  Our contribution......Page 701
  Overview of our techniques......Page 702
  Related work......Page 703
  Organization......Page 704
 Learning Euclidean metric spaces with perfect information......Page 705
  Euclidean spaces and Lipschitz partitions......Page 706
  The algorithm: Combining Lipschitz and pseudoregular partitions......Page 707
 Learning Euclidean metric spaces with imperfect information......Page 708
  Isoperimetry and the diameter of embeddings......Page 709
  The algorithm......Page 711
 Introduction......Page 713
 Persistence modules......Page 715
 The matching distance......Page 717
 The arrangement......Page 718
 Maximization......Page 722
 Discussion......Page 726
 Introduction......Page 729
  Related work......Page 730
  Our contributions and outline......Page 731
 A generalized median problem......Page 732
  On reducing the size of the input sets......Page 735
  Probabilistic smallest enclosing ball......Page 736
  Probabilistic support vector data description......Page 738
 Conclusion and open problems......Page 740
 Introduction......Page 743
 Our algorithm......Page 746
 Proof of invariants......Page 750
 Minimum bottleneck matching......Page 751
p049-DeMesmay......Page 757
 Introduction......Page 758
 Preliminaries......Page 759
 Trivial sublink......Page 760
 The defect......Page 761
 The reduction......Page 763
  Satisfiable implies small defect......Page 767
  Small defect implies satisfiable......Page 769
 Intermediate invariants......Page 771
 Unlinking, 4-ball Euler characteristic, and intermediate invariants......Page 772
 Introduction......Page 777
 Proof of Theorem 1.3......Page 779
 Natural Grids......Page 780
 Lower Bound Construction......Page 783
 Concluding Remarks......Page 786
 Introduction......Page 789
  Some convexity spaces......Page 792
  Upper bound......Page 793
  Lower bound......Page 794
  The necessity of assumptions......Page 795
 Proof of upper bound......Page 796
 Proof of lower bound......Page 797
  The threshold 1/2 is sharp......Page 798
 Future research......Page 799
 Radon, Helly and VC......Page 801
 The chromatic number of the Kneser graph......Page 802
 Introduction......Page 803
  Our Approach......Page 805
 Ray Shooting: Static Structure......Page 807
 Semi-Dynamic Ray Shooting for B >= log^{8}n: Main Idea......Page 810
 Ray Shooting for B >= log^{8}n: Fully-Dynamic Structure......Page 812
 Missing Details......Page 815
 Introduction......Page 819
  Ortho-Radial Drawings and Representations......Page 822
 Finding Monotone Cycles......Page 824
 Rectangulation......Page 827
  1st Improvement – Faster Validity Test......Page 828
 Conclusion......Page 830
 Introduction......Page 833
  Families of curves......Page 834
  Our results......Page 835
 A bounding function for grounded curves – Proofs of Theorems 1 and 5......Page 836
 Magical graphs – Proof of Theorem 2......Page 838
 Bounding function for curves that intersect a vertical line–Proof of Theorem 3......Page 843
 Construction of double-magical graphs–Proof of Theorem 4......Page 845
 Concluding remarks......Page 847
 Introduction......Page 851
 Preliminaries......Page 853
 Strong Collapse of a Flag complex......Page 855
  A new construction......Page 858
 Computational experiments......Page 861
 Introduction......Page 867
 Ham Sandwich Cuts in horizontal subspaces......Page 871
 Application: bisecting lines in space......Page 872
 Center Transversals in general subspaces......Page 873
 Sections in product bundles......Page 875
 Application: bisections with several cuts......Page 876
 Introduction......Page 883
   A Lower Bound of Omega(1/rho)......Page 884
   On a Distribution of Inputs: Small Summaries for Halfspaces......Page 885
  New Definitions on Range Spaces......Page 887
  Analysis......Page 888
   Bounding the Size......Page 889
   A Remark......Page 890
 Bridging distribution and finite-set disagreement coefficients......Page 891
 o(1/rho)-size summaries for halfspace ranges......Page 892
 A lower bound with disagreement coefficients......Page 894
 Introduction......Page 897
 Filtrations and interleaving distance......Page 899
  Definition......Page 901
  Weighted Vietoris-Rips filtrations......Page 903
  The distance to measure (DTM)......Page 905
  DTM-filtrations......Page 906
  Stability when p=1......Page 907
  Stability when p>1......Page 909
 Conclusion......Page 910
 Introduction......Page 913
 Preliminaries......Page 916
 Solving the Main Sub-Problem......Page 918
  The Query Algorithm......Page 920
 Reducing the Query Time to O(log n)......Page 924
 Introduction......Page 927
  Related work and our contributions......Page 928
  Notations......Page 929
 The exact algorithm......Page 930
  First update......Page 933
  Second update......Page 934
  Putting everything together......Page 935
 The approximation algorithm......Page 936
  Approximate update......Page 937
  Putting everything together......Page 938
 Introduction......Page 941
  Related work and our contributions......Page 942
  Preliminaries......Page 943
 Translation RCP queries for polygons......Page 944
  Reduction to (co-)wedge translation queries......Page 945
  Handling wedge translation queries......Page 946
  Handling co-wedge translation queries......Page 949
 Translation RCP queries for smooth convex bodies......Page 950
  Handling short-answer queries......Page 951
  Handling long-answer queries......Page 952
  Proof of Theorem 20......Page 953
 Introduction......Page 957
 The case of pseudoplanes......Page 960
  An extension of the dual version of the Lovász Lemma......Page 961
  The dual version of the Crossing Lemma......Page 966
 Discussion......Page 969
p063-Becker......Page 973
 Introduction......Page 974
 Circles in a Square: Split Packing......Page 975
 Circles in a Circle: Boundary/Ring Packing......Page 976
 The Video......Page 977
 Introduction......Page 979
  Counting Minimal-Perimeter Polyominoes......Page 980
 The Video......Page 981
 Introduction......Page 983
 Results......Page 984
 The Fréchet-distance......Page 985
 The Fréchet-distance for Simple Polygons......Page 986
 The k-Fréchet-distance......Page 987
 Fréchet View – the Implementation......Page 988