Vol. 11 No. 1 (2020)

DOI: https://doi.org/10.20382/jocg.v11i1

Published: 2020-03-27

Articles

On optimal polyline simplification using the Hausdorff and Fréchet distance

Marc van Kreveld, Maarten Löffler, Lionov Wiratma

1–25
- PDF
Stable-matching Voronoi diagrams: Combinatorial complexity and algorithms

Gill Barequet, David Eppstein, Michael Goodrich, Nil Mamano

26–59
- PDF
New lower bounds for the number of pseudoline arrangements

Adrian Dumitrescu, Ritankar Mandal

60–92
- PDF
Rigid foldability is NP-hard

Hugo Akitaya, Erik Demaine, Takashi Horiyama, Thomas Hull, Jason Ku, Tomohiro Tachi

93–124
- PDF
Determining hyperbolicity of compact orientable 3-manifolds with torus boundary

Robert Cyrus Haraway, III

125–136
- PDF
On the planar edge-length ratio of planar graphs

Manuel Borrazzo, Fabrizio Frati

137–155
- PDF
Algorithms for the discrete Fréchet distance under translation

Omrit Filtser, Matthew Katz

156–175
- PDF
Spectral sparsification of simplicial complexes for clustering and label propagation

Braxton Osting, Sourabh Palande, Bei Wang

176–211
- PDF
Expected complexity of routing in $\Theta_6$ and half-$\Theta_6$ graphs

Prosenjit Bose, Jean-Lou De Carufel, Olivier Devillers

212–234
- PDF
- Maple Worksheet
A divide-and-conquer algorithm for two-point L1 shortest path queries in polygonal domains

Haitao Wang

235–282
- PDF
An improved cost function for hierarchical cluster trees

Dingkang Wang, Yusu Wang

283–331
- PDF
Four pages are indeed necessary for planar graphs

Michael Kaufmann, Michael Bekos, Fabian Klute, Sergey Pupyrev, Chrysanthi Raftopoulou, Torsten Ueckerdt

332–353
- PDF
Aligned plane drawings of the generalized Delaunay-graphs for pseudo-disks

Balázs Keszegh, Dömötör Pálvölgyi

354–370
- PDF
NP-completeness of slope-constrained drawing of complete graphs

Cédric Pilatte

371–396
- PDF
Face flips in origami tessellations

Hugo A. Akitaya, Vida Dujmović, David Eppstein, Thomas C. Hull, Kshitij Jain, Anna Lubiw

397–417
- PDF
Faster algorithms for some optimization problems on collinear points

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

418–432
- PDF
Drawing graphs on few lines and few planes

Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, Alexander Wolff

433–475
- PDF
- Supplementary Material
4-Connected triangulations on few lines

Stefan Felsner

476–492
- PDF
On the average complexity of the $k$-level

Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher, Patrick Schnider, Raphael Steiner, Pavel Valtr

493–506
- PDF
A simple randomized $O(n \log n)$–time closest-pair algorithm in doubling metrics

Michiel Smid, Anil Maheshwari, Wolfgang Mulzer

507–524
- PDF
Time-space trade-offs for computing Euclidean minimum spanning trees

Bahareh Banyassady, Luis Barba, Wolfgang Mulzer

525–547
- PDF
On the classification of motions of paradoxically movable graphs

Georg Grasegger, Jan Legerský, Josef Schicho

548–575
- PDF
Halving balls by a hyperplane in deterministic linear time

Michael Hoffmann, Vincent Kusters, Tillmann Miltzow

576–614
- PDF
An explicit PL-embedding of the square flat torus into $\mathbb{E}^3$

Tanessi Quintanar

615–628
- PDF
Approximate greedy clustering and distance selection for graph metrics

David Eppstein, Sariel Har-Peled, Anastasios Sidiropoulos

629–652
- PDF
Corrigendum to: Approximating minimum-area rectangular and convex containers for packing convex polygons

Helmut Alt, Mark de Berg, Christian Knauer

653–655
- PDF