Last update:
Sat Nov 23 16:56:14 MST 2024
C. M. Hoffmann and
P. J. Vermeer Eliminating Extraneous Solutions in
Curve and Surface Operations . . . . . . 47--66
G. Van\ve\vcek, Jr. Brep-index: a Multidimensional Space
Partitioning Tree (revised) . . . . . . 243--262
Dinesh Manocha and
John F. Canny A New Approach to Surface Intersection 491--516
K. Sugihara Voronoi Diagrams in a River . . . . . . 29--48
T. K. Dey and
C. Bajaj On Good Triangulations in Three
Dimensions . . . . . . . . . . . . . . . 75--95
O. Devillers Randomization yields simple $ O(n \log^*
n) $ algorithms for difficult $ \Omega
(n) $ problems . . . . . . . . . . . . . 97--111
Y.-J. Chiang and
R. Tamassia Dynamization of the trapezoid method for
planar point location . . . . . . . . . 311--333
Kwong-Fai Chan and
Tak Wah Lam An on-line algorithm for navigating in
an unknown environment . . . . . . . . . 227--244
R. Janardan On maintaining the width and diameter of
a planar point-set online . . . . . . . 331--344
Naoyoshi Kanamaru and
Takao Nishizeki and
Tetsuo Asano Efficient enumeration of grid points in
a convex polygon and its application to
integer programming . . . . . . . . . . 69--85
Kokichi Sugihara and
Masao Iri A Robust Topology-Oriented Incremental
Algorithm for Voronoi Diagrams . . . . . 179--228
S. J. Fortune Numerical Stability of Algorithms for
$2$D Delaunay triangulations . . . . . . 193--213
Y. A. Teng and
D. Mount and
E. Puppo and
L. S. Davis Parallelizing an algorithm for
visibility on polyhedral terrain . . . . ??
Esther M. Arkinn and
Joseph S. B. Mitchell and
Steven S. Skiena Guest Editors' Foreword . . . . . . . . 1
Scott A. Mitchell Finding a Covering Triangulation Whose
Maximum Angle is Provably Small . . . . 5
Vadim Shapiro Maintenance of Geometric Representations
Through Space Decompositions . . . . . . 21
Klara Kedem and
Daniel Cohen Efficient Bitmap Resemblance Under
Translations . . . . . . . . . . . . . . 57
Y. Ansel Teng and
David Mount and
Enrico Puppo and
Larry S. Davis Parallelizing an Algorithm for
Visibility on Polyhedral Terrain . . . . 75
Yi-Jen Chiang and
Roberto Tamassia Optimal Shortest Path and Minimum ---
Link Path Queries between Two Convex
Polygons inside a Simple Polygonal
Obstacle . . . . . . . . . . . . . . . . 85
Ming Lin and
Dinesh Manocha Efficient Contact Determination in
Dynamic Environments . . . . . . . . . . 123
Prosenjit Bose and
Leonidas Guibas and
Anna Lubiw and
Mark Overmars and
Diane Souvaine and
Jorge Urrutia The Floodlight Problem . . . . . . . . . 153--163
Joseph O'Rourke Computational Geometry Column $ 30 $ . . 165
Tamal K. Dey Efficient Algorithms to Detect
Null-Homologous Cycles on $2$-Manifolds 167
Mark de Berg and
Dan Halperin and
Mark Overmars and
Marc van Kreveld Sparse Arrangements and the Number of
Views of Polyhedral Scenes . . . . . . . 175
Goos Kant A More Compact Visibility Representation 197
Marek Chrobak and
Goos Kant Convex Grid Drawings of $3$-Connected
Planar Graphs . . . . . . . . . . . . . 211
Susan Hert and
Vladimir Lumelsky Planar Curve Routing for Tethered-Robot
Motion Planning . . . . . . . . . . . . 225
Binhai Zhu Approximating Convex Polyhedra with
Axis-Parallel Boxes . . . . . . . . . . 253
Steven Fortune Editor's Foreword . . . . . . . . . . . 269
Joonsoo Choi and
Juergen Sellen and
Chee-Keng Yap Approximate Euclidean Shortest Paths in
$3$-Space . . . . . . . . . . . . . . . 271
Gautam Das and
Giri Narasimhan A Fast Algorithm for Constructing Sparse
Euclidean Spanners . . . . . . . . . . . 297
Joseph S. B. Mitchell and
David M. Mount and
Subhash Suri Query-Sensitive Ray Shooting . . . . . . 317
Oswin Aichholzer and
Helmut Alt and
Günter Rote Matching Shapes with a Reference Point 349
Herbert Edelsbrunner and
Nimish R. Shah Triangulating Topological Spaces . . . . 365
Joseph O'Rourke Computational Geometry Column $ 31 $ . . 379
Vadim Shapiro Errata: ``Maintenance of Geometric
Representations Through Space
Decompositions'' . . . . . . . . . . . . 383
Jun-Ya Takahashi and
Hitoshi Suzuki and
Takao Nishizeki Shortest Non-Crossing Rectilinear Paths
in Plane Regions . . . . . . . . . . . . 419
Prosenjit Gupta and
Ravi Janardan and
Michiel Smid and
Bhaskar Dasgupta The Rectangle Enclosure and
Point-Dominance Problems Revisited . . . 437
Joseph L. Ganley and
J. P. Cohoon Improved Computation of Optimal
Rectilinear Steiner Minimal Trees . . . 457
J. Mark Keil Covering Orthogonal Polygons with
Non-Piercing Rectangles . . . . . . . . 473
David Eppstein Faster Circle Packing with Application
to Nonobtuse Triangulation . . . . . . . 485
Muhammad H. Alsuwaiyel Two Algorithms for the Sum of Diameters
Problem and a Related Problem . . . . . 493
Joseph O'Rourke Computational Geometry Column $ 32 $ . . 509
Leizhen Cai and
J. Mark Keil Computing Visibility Information in an
Inaccurate Simple Polygon . . . . . . . 515
Vitit Kantabutra Reaching a Point with an Unanchored
Robot Arm in a Square . . . . . . . . . 539
Jurek Czyzowicz and
Hazel Everett and
Jean-Marc Robert Separating Translates in the Plane:
Combinatorial Bounds and an Algorithm 551
Frank Follert and
Elmar Schömer and
Jürgen Sellen and
Michiel Smid and
Christian Thiel Computing a Largest Empty Anchored
Cylinder, and Related Problems . . . . . 563
D. T. Lee and
C. D. Yang and
C. K. Wong Finding Rectilinear Paths Among
Obstacles in a Two-Layer Interconnection
Model . . . . . . . . . . . . . . . . . 581
Wenping Wang and
Barry Joe and
Ronald Goldman Rational Quadratic Parameterizations of
Quadrics . . . . . . . . . . . . . . . . 599
Anonymous Author Index . . . . . . . . . . . . . . 621
S. P. Fekete and
J. S. B. Mitchell Histogram decomposition and
stereolithography . . . . . . . . . . . ??
Michael T. Goodrich An Improved Ray Shooting Method for
Constructive Solid Geometry Models Via
Tree Contraction . . . . . . . . . . . . 1
James Abello and
Vladimir Estivill-Castro and
Thomas Shermer and
Jorge Urrutia Illumination of Orthogonal Polygons with
Orthogonal Floodlights . . . . . . . . . 25
Franck Nielsen and
Mariette Yvinec An Output-Sensitive Convex Hull
Algorithm for Planar Objects . . . . . . 39
Per-Olof Fjällström and
Jan Petersson and
Larsgunnar Nilsson and
Zhi-Hua Zhong Evaluation of Range Searching Methods
for Contact Searching in Mechanical
Engineering . . . . . . . . . . . . . . 67
L. H. Tseng and
P. Heffernan and
D. T. Lee Two-Guard Walkability of Simple Polygons 85
Nina Amenta and
Steven Fortune Guest Editors' Foreword . . . . . . . . 117
D. T. Lee and
Chin-Fang Shen and
Dennis S. Sheu Geosheet: a Distributed Visualization
Tool for Geometric Algorithms . . . . . 119
Leonidas J. Guibas and
David H. Marimont Rounding Arrangements Dynamically . . . 157
Leonidas J. Guibas and
Dan Halperin and
Hirohisa Hirukawa and
Jean-Claude Latombe and
Randall H. Wilson Polyhedral Assembly Partitioning Using
Maximally Covered Cells in Arrangements
of Convex Polytopes . . . . . . . . . . 179
Jules Vleugels and
Mark Overmars Approximating Voronoi Diagrams of Convex
Sites in Any Dimension . . . . . . . . . 201
Ioannis Z. Emiris A Complete Implementation for Computing
General Dimensional Convex Hulls . . . . 223
Ernst P. Mücke A Robust Implementation for
Three-Dimensional Delaunay
Triangulations . . . . . . . . . . . . . 255
Danny Z. Chen Determining Weak Visibility of a Polygon
from an Edge in Parallel . . . . . . . . 277
Wei Chen and
Koichi Wada and
Kimio Kawaguchi and
Danny Z. Chen Finding the Convex Hull of Discs in
Parallel . . . . . . . . . . . . . . . . 305
Olivier Devillers and
Mordecai J. Golin Dog Bites Postman: Point Location in the
Moving Voronoi Diagram and Related
Problems . . . . . . . . . . . . . . . . 321
Esther M. Arkin and
Henk Meijer and
Joseph S. B. Mitchell and
David Rappaport and
Steven S. Skiena Decision Trees for Geometric Models . . 343
Gerhard Albers and
Leonidas J. Guibas and
Joseph S. B. Mitchell and
Thomas Roos Voronoi Diagrams of Moving Points . . . 365
Joseph O'Rourke Computational Geometry Column $ 33 $ . . 381
Ming C. Lin and
Dinesh Manocha Guest Editors' Foreword . . . . . . . . 385
Mu Hong and
Thomas W. Sederberg and
Krzysztof S. Klimaszewski and
Kazufumi Kaneda Triangulation of Branching Contours
Using Area Minimization . . . . . . . . 389
Sylvain Petitjean A Computational Geometric Approach to
Visual Hulls . . . . . . . . . . . . . . 407
Susan Hert and
Vladimir Lumelsky Polygon Area Decomposition for
Multiple-Robot Workspace Division . . . 437
Mark De Berg and
Henk Meijer and
Mark Overmars and
Gordon Wilfong Computing the Angularity Tolerance . . . 467
Toni Jabbour and
Christian Mascle and
Roland Maranzana A Database for the Representation of
Assembly Features in Mechanical Products 483
Mark T. Ensz and
Duane W. Storti and
Mark A. Ganter Implicit Methods for Geometry Creation 509
Jai Menon and
Baining Guo Free-Form Modeling in Bilateral Brep and
CSG Representation Schemes . . . . . . . 537
Guy Evans and
Alan Middleditch and
Nick Miles Stable Computation of the $2$D Medial
Axis Transform . . . . . . . . . . . . . 577
Rida T. Farouki and
Rajesh Ramamurthy Specified-Precision Computation of
Curve/Curve Bisectors . . . . . . . . . 599
Gill Barequet DCEL: a Polyhedral Database and
Programming Environment . . . . . . . . 619
Pankaj K. Agarwal and
Joseph O'Rourke Computational Geometry Column $ 34 $ . . 637
Anonymous Author Index Volume 8 (1998) . . . . . . 643
S. P. Fekete and
H. Meijer Rectangle and Box Visibility Graphs in
$3$D . . . . . . . . . . . . . . . . . . 1
M. J. Atallah An Improved Hypercube Bound for
Multisearching and Its Applications . . 29
O. Devillers and
M. J. Katz Optimal Line Bipartitions of Point Sets 39
D. Kirkpatrick and
J. Snoeyink Computing Constrained Shortest Segments:
Butterfly Wingspans in Logarithmic Time 53
X. H. Tan Edge Guards in Straight Walkable
Polygons . . . . . . . . . . . . . . . . 63
B. K. Bhattacharya and
A. Mukhopadhyay and
G. T. Toussaint Computing a Shortest Weakly Externally
Visible Line Segment for a Simple
Polygon . . . . . . . . . . . . . . . . 81
M. Smid and
R. Janardan On the Width and Roundness of a Set of
Points in the Plane . . . . . . . . . . 97
A. Glozman and
K. Kedem and
G. Shpitalnik Computing a Double-Ray Center for a
Planar Point Set . . . . . . . . . . . . 109
V. Shapiro Well-Formed Set Representations of
Solids . . . . . . . . . . . . . . . . . 125
Y. Kusakari and
H. Suzuki and
T. Nishizeki A Shortest Pair of Paths on the Plane
with Obstacles and Crossing Areas . . . 151
E. Kranakis and
J. Urrutia Isomorphic Triangulations with Small
Number of Steiner Points . . . . . . . . 171
J. Czyzowicz and
I. Stojmenovic and
J. Urrutia Immobilizing a Shape . . . . . . . . . . 181
E. F. Grove and
T. M. Murali and
J. S. Vitter The Object Complexity Model for
Hidden-Surface Removal . . . . . . . . . 207
M. Segal On Piercing Sets of Axis-Parallel
Rectangles and Rings . . . . . . . . . . 219
O. Aichholzer and
F. Aurenhammer and
D. Z. Chen and
D. T. Lee and
E. Papadopoulou Skew Voronoi Diagrams . . . . . . . . . 235
E. Assa and
M. J. Katz $3$-Piercing of $d$-Dimensional Boxes
and Homothetic Triangles . . . . . . . . 249
G. Narasimhan On Hamiltonian Triangulations in Simple
Polygons . . . . . . . . . . . . . . . . 261
D. Richards and
J. S. Salowe Mixed Spanning Trees in Theory and
Practice . . . . . . . . . . . . . . . . 277
N. Baek and
S.-Y. Shin and
K.-Y. Chwa On Computing Translational Swept Volumes 293
X. Tan and
T. Hirata and
Y. Inagaki Corrigendum to ``An Incremental
Algorithm for Constructing Shortest
Watchman Routes'' . . . . . . . . . . . 319
Pankaj K. Agarwal Guest Editor's Foreword . . . . . . . . 325
Fausto Bernardini and
Chandrajit L. Bajaj and
Jindong Chen and
Daniel R. Schikore Automatic Reconstruction of $3$D CAD
Models From Digital Scans . . . . . . . 327
Michael H. Goldwasser and
Rajeev Motwani Complexity Measures for Assembly
Sequences . . . . . . . . . . . . . . . 371
Stina Bridgeman and
Ashim Garg and
Roberto Tamassia A Graph Drawing and Translation Service
on the World Wide Web . . . . . . . . . 419
Howie Choset Nonsmooth Analysis, Convex Analysis, and
their Applications to Motion Planning 447
Leonidas J. Guibas and
Jean-Claude Latombe and
Steven M. Lavalle and
David Lin and
Rajeev Motwani A Visibility-Based Pursuit-Evasion
Problem . . . . . . . . . . . . . . . . 471
David Hsu and
Jean-Claude Latombe and
Rajeev Motwani Path Planning in Expansive Configuration
Spaces . . . . . . . . . . . . . . . . . 495
Joseph O'Rourke Computational Geometry Column $ 35 $ . . 513
M. Bern and
D. Eppstein and
S.-H. Teng Parallel Construction of Quadtrees and
Quality Triangulations . . . . . . . . . 517
E. Papadopoulou $k$-Pairs Non-Crossing Shortest Paths in
a Simple Polygon . . . . . . . . . . . . 533
F. D'Amore and
R. Giaccio Intersection Problems on Segments Under
Boundary Updates with Application to
Persistent Lists . . . . . . . . . . . . 553
G. L. Miller and
D. Talmor and
S.-H. Teng Data Generation for Geometric Algorithms
on Non-Uniform Distributions . . . . . . 577
H. Martini and
V. Soltan Minimum Number of Pieces in a Convex
Partition of a Polygonal Domain . . . . 599
J. O'Rourke Computational Geometry Column $ 36 $ . . 615
Anonymous Author Index . . . . . . . . . . . . . . 619
M. Müller-Hannemann and
K. Weihe Quadrangular Refinements of Convex
Polygons with an Application to
Finite-Element Meshes . . . . . . . . . 1
J.-D. Boissonnat and
J. Czyzowicz and
O. Devillers and
J. Urrutia and
M. Yvinec Computing Largest Circles Separating Two
Sets of Segments . . . . . . . . . . . . 41
D. Bremner and
T. Shermer Point Visibility Graphs and $O$-Convex
Cover . . . . . . . . . . . . . . . . . 55
A. Kaneko and
M. Kano and
K. Yoshimoto Alternating Hamilton Cycles with Minimum
Number of Crossings in the Plane . . . . 73
G. Srinivasaraghavan and
A. Mukhopadhyay Orthogonal Edge Visibility Graphs of
Polygons with Holes . . . . . . . . . . 79
E. D. Demaine and
J. O'Rourke Computational Geometry Column $ 37 $ . . 103
H. Ratschek and
J. Rokne Exact and Optimal Convex Hulls in $2$D 109
N. Baek and
S.-Y. Shin and
K.-Y. Chwa Three-Dimensional Topological Sweep for
Computing Rotational Swept Volumes of
Polyhedral Objects . . . . . . . . . . . 131
L. G. Aleksandrov and
H. N. Djidjev and
J.-R. Sack An $ O(n \log n) $ Algorithm for Finding
a Shortest Central Link Segment . . . . 157
S. K. Wismath Point and Line Segment Reconstruction
from Visibility Information . . . . . . 189
J.-H. Lee and
S.-M. Park and
K.-Y. Chwa Searching a Polygonal Room with One Door
by a $1$-Searcher . . . . . . . . . . . 201
J. O'Rourke Computational Geometry Column $ 38 $ . . 221
S.-H. Teng Guest Editor's Foreword . . . . . . . . 225
S.-H. Teng and
C. W. Wong Unstructured Mesh Generation: Theory,
Practice, and Perspectives . . . . . . . 227
H. Edelsbrunner and
R. Waupotitsch Adaptive Simplicial Grids from
Cross-Sections of Monotone Complexes . . 267
M. Müller-Hannemann High Quality Quadrilateral Surface
Meshing Without Template Restrictions: a
New Approach Based on Network Flow
Techniques . . . . . . . . . . . . . . . 285
A. Sheffer and
M. Bercovier and
T. Blacker and
J. Clements Virtual Topology Operators for Meshing 309
M. Berzins Solution-Based Mesh Quality Indicators
for Triangular and Tetrahedral Meshes 333
M. Bern and
D. Eppstein Quadrilateral Meshing by Circle Packing 347
L. A. Freitag and
C. Ollivier-Gooch A Cost/Benefit Analysis of Simplicial
Mesh Improvement Techniques as Measured
by Solution Efficiency . . . . . . . . . 361
R. Schneiders Octree-Based Hexahedral Mesh Generation 383
S. A. Mitchell High Fidelity Interval Assignment . . . 399
K. Shimada and
A. Yamada and
T. Itoh Anisotropic Triangulation of Parametric
Surfaces via Close Packing of Ellipsoids 417
J. O'Rourke Computational Geometry Column $ 39 $ . . 441
M. A. Lopez and
S. Reisner Efficient Approximation of Convex
Polygons . . . . . . . . . . . . . . . . 445
C. Ó Dúnlaing and
C. Watt and
D. Wilkins Homeomorphism of $2$-Complexes is
Equivalent to Graph Isomorphism . . . . 453
C. N. De Meneses and
C. C. De Souza Exact Solutions of Rectangular
Partitions via Integer Programming . . . 477
S. Bespamyatnikh and
K. Kedem and
M. Segal and
A. Tamir Optimal Facility Location Under Various
Distance Functions . . . . . . . . . . . 523
M. Keil and
D. M. Mount and
S. K. Wismath Visibility Stabs and Depth-First
Spiralling on Line Segments in Output
Sensitive Time . . . . . . . . . . . . . 535
T. C. Biedl and
B. P. Madden and
I. G. Tollis The Three-Phase Method: a Unified
Approach to Orthogonal Graph Drawing . . 553
B. Ben-Moshe and
M. J. Katz and
M. Segal Obnoxious Facility Location: Complete
Service with Minimal Harm . . . . . . . 581
D. M. Mount and
N. S. Netanyahu and
C. D. Piatko and
R. Silverman and
A. Y. Wu Quantile Approximation for Robust
Statistical Estimation and $k$-Enclosing
Problems . . . . . . . . . . . . . . . . 593
L.-E. Andersson and
T. J. Peters and
N. F. Stewart Equivalence of Topological Form for
Curvilinear Geometric Objects . . . . . 609
G. Di Battista and
A. Garg and
G. Liotta and
A. Parise and
R. Tamassia and
E. Tassinari and
F. Vargiu and
L. Vismara Drawing Directed Acyclic Graphs: An
Experimental Study . . . . . . . . . . . 623
J. O'Rourke Computational Geometry Column $ 40 $ . . 649
Anonymous Author Index . . . . . . . . . . . . . . 653
Renato Pajarola and
Peter Widmayer Virtual Geoexploration: Concepts and
Design Choices . . . . . . . . . . . . . 1--14
Roberto Tamassia and
Luca Vismara A Case Study in Algorithm Engineering
for Geometric Computing . . . . . . . . 15--70
Kiyoko F. Aoki and
D. T. Lee Towards Web-Based Computing . . . . . . 71--104
S. Krishnan and
D. Manocha and
M. Gopi and
T. Culver and
J. Keyser BOOLE: a Boundary Evaluation System for
Boolean Combinations of Sculptured
Solids . . . . . . . . . . . . . . . . . 105
Tetsuo Asano and
Danny Z. Chen and
Naoki Katoh and
T. Tokuyama Efficient Algorithms for
Optimization-Based Image Segmentation 145--166
Sung Kwon Kim and
Chan-Su Shin and
Tae-Cheon Yang and
others Labeling a Rectilinear Map with Sliding
Labels . . . . . . . . . . . . . . . . . 167--179
Tycho Strijk and
Alexander Wolff Labeling Points with Circles . . . . . . 181--195
Otfried Cheong and
René van Oostrum Reaching a Polygon with Directional
Uncertainty . . . . . . . . . . . . . . 197--214
Vadim Shapiro A Convex Deficiency Tree Algorithm for
Curved Polygons . . . . . . . . . . . . 215--238
Joseph O'Rourke Computational Geometry Column $ 41 $ . . 239--242
John Hershberger Guest Editor's Foreword . . . . . . . . 243--244
Christoph Burnikel and
Stefan Funke and
Michael Seel Exact Geometric Computation Using
Cascading . . . . . . . . . . . . . . . 245--266
Marcus Vinícius Alvim Andrade and
Jorge Stolfi Exact Algorithms for Circles on the
Sphere . . . . . . . . . . . . . . . . . 267--290
Timothy M. Chan On Enumerating and Selecting Distances 291--304
A. Crauser and
P. Ferragina and
K. Mehlhorn and
U. Meyer and
E. A. Ramos Randomized External-Memory Algorithms
for Line Segment Intersection and Other
Geometric Problems . . . . . . . . . . . 305--337
Sunil Arya and
Siu-Wing Cheng and
David M. Mount Approximation Algorithm for
Multiple-Tool Milling . . . . . . . . . 339--372
Mikhail J. Atallah and
Danny Z. Chen On Connecting Red and Blue Rectilinear
Polygonal Obstacles with Nonintersecting
Monotone Rectilinear Paths . . . . . . . 373--400
Alejandro López-Ortiz and
Sven Schuierer Lower Bounds for Streets and Generalized
Streets . . . . . . . . . . . . . . . . 401--421
Thomas Christof and
Gerhard Reinelt Decomposition and Parallelization
Techniques for Enumerating the Facets of
Combinatorial Polytopes . . . . . . . . 423--437
J. Rafael Sendra and
Carlos Villarino Optimal Reparametrization of Polynomial
Algebraic Curves . . . . . . . . . . . . 439--453
Binhai Zhu and
C. K. Poon Efficient Approximation Algorithms for
Two-Label Point Labeling . . . . . . . . 455--464
Gill Barequet and
Sariel Har-Peled Polygon Containment and Translational
Min-Hausdorff-Distance Between Segment
Sets are $3$ SUM-Hard . . . . . . . . . 465--474
Jiaye Wang and
Ding Yuan Liu and
Wenping Wang Computing an Almost Minimum Set of
Spanning Line Segments of a Polyhedron 475--485
Wei Chen and
Xiaowen Deng and
Koichi Wada and
K. Kawaguchi Constructing a Strongly Convex Superhull
of Points . . . . . . . . . . . . . . . 487--502
Evantha Papadopoulou and
D. T. Lee The $ L_{\infty } $ Voronoi Diagram of
Segments and VLSI Applications . . . . . 503--528
Ichiro Suzuki and
Yuichi Tazoe and
Masafumi Yamashita and
T. Kameda Searching a Polygonal Region from the
Boundary . . . . . . . . . . . . . . . . 529--553
Olivier Devillers and
Philippe Guigue The Shuffling Buffer . . . . . . . . . . 555--572
Joseph S. B. Mitchell and
Joseph O'Rourke Computational Geometry Column $ 42 $ . . 573--582
Kurt Mehlhorn and
Stefan Meiser and
Ronald Rasch Furthest Site Abstract Voronoi Diagrams 583
Danny Z. Chen and
Ovidiu Daescu and
Kevin S. Klenk On Geometric Path Query Problems . . . . 617
Sándor P. Fekete and
Joseph S. B. Mitchell Terrain Decomposition and Layered
Manufacturing . . . . . . . . . . . . . 647
Michael Murphy and
David M. Mount and
Carl W. Gable A Point-Placement Strategy for
Conforming Delaunay Tetrahedralization 669
Anonymous Author Index . . . . . . . . . . . . . . 683
Mark de Berg and
Stefan Schirra Guest Editor's Foreword . . . . . . . . 1
David Kirkpatrick and
Jack Snoeyink and
Bettina Speckmann Kinetic Collision Detection for Simple
Polygons . . . . . . . . . . . . . . . . 3
Srinivas R. Doddi and
Madhav V. Marathe and
Bernard M. E. Moret Point Set Labeling with Specified
Positions . . . . . . . . . . . . . . . 29
Timothy M. Chan Approximating the Diameter, Width,
Smallest Enclosing Cylinder, and
Minimum-Width Annulus . . . . . . . . . 67
Steven M. Lavalle and
Borislav H. Simov and
Giora Slutzki An Algorithm for Searching a Polygonal
Region with a Flashlight . . . . . . . . 87
Peter Brass and
Christian Knauer Testing the Congruence of
$d$-Dimensional Point Sets . . . . . . . 115
Nina Amenta and
Sunghee Choi and
Tamal K. Dey and
Naveen Leekha A Simple Algorithm for Homeomorphic
Surface Reconstruction . . . . . . . . . 125
Afra Zomorodian and
Herbert Edelsbrunner Fast Software for Box Intersections . . 143
David Binger Polyhedra with Unguarded Interiors . . . 173
Mark Keil and
Jack Snoeyink On the Time Bound for Convex
Decomposition of Simple Polygons . . . . 181
Olivier Devillers On Deletion in Delaunay Triangulations 193
Jong-Sung Ha and
Sung-Yong Shin Edge Advancing Rules for Intersecting
Spherical Convex Polygons . . . . . . . 207
Sergei Bespamyatnikh An Optimal Morphing Between Polylines 217
Olivier Devillers and
Pedro A. Ramos Computing Roundness is Easy if the Set
is Almost Round . . . . . . . . . . . . 229
Xuehou Tan Finding an Optimal Bridge Between Two
Polygons . . . . . . . . . . . . . . . . 249
Joseph O'Rourke Computational Geometry Column $ 43 $ . . 263
Takeshi Tokuyama Guest Editor's Foreword . . . . . . . . 267
Alexander Wolff and
Michael Thon and
Yinfeng Xu A Simple Factor-$ \frac {2}{3} $
Approximation Algorithm for Two-Circle
Point Labeling . . . . . . . . . . . . . 269
Prosenjit Bose and
Andrej Brodnik and
Svante Carlsson and
Erik D. Demaine and
Rudolf Fleischer and
Alejandro López-Ortiz and
Pat Morin and
J. Ian Munro Online Routing in Convex Subdivisions 283
Prosenjit Bose and
Pat Morin An Improved Algorithm for Subdivision
Traversal without Extra Storage . . . . 297
Danny Z. Chen and
Xiaobo S. Hu and
Xiaodong Wu Optimal Polygon Cover Problems and
Applications . . . . . . . . . . . . . . 309
Sang-Min Park and
Jae-Ha Lee and
Kyung-Yong Chwa Searching a Room by Two Guards . . . . . 339
Tamal K. Dey and
Rephael Wenger Fast Reconstruction of Curves with Sharp
Corners . . . . . . . . . . . . . . . . 353
Adrian Dumitrescu and
János Pach Partitioning Colored Point Sets into
Monochromatic Parts . . . . . . . . . . 401
Danny Z. Chen and
Jie Wang and
Xiaodong Wu Image Segmentation with
Asteroidality/Tubularity and Smoothness
Constraints . . . . . . . . . . . . . . 413
Naoki Katoh and
Hisao Tamaki and
Takeshi Tokuyama Parametric Polymatroid Optimization and
Its Geometric Applications . . . . . . . 429
Prosenjit Bose and
Luc Devroye and
William Evans Diamonds are Not a Minimum Weight
Triangulation's Best Friend . . . . . . 445
Hiroshi Imai and
Tomonari Masada and
Fumihiko Takeuchi and
Keiko Imai Enumerating Triangulations in General
Dimensions . . . . . . . . . . . . . . . 455
Jia F. Weng Generalized Melzak's Construction in the
Steiner Tree Problem . . . . . . . . . . 481
Grégoire Malandain and
Jean-Daniel Boissonnat Computing the Diameter of a Point Set 489
Atsushi Koike and
Shin-Ichi Nakano and
Takao Nishizeki and
Takeshi Tokuyama and
Shuhei Watanabe Labeling Points with Rectangles of
Various Shapes . . . . . . . . . . . . . 511
Anonymous Author Index . . . . . . . . . . . . . . 529
D. T. Lee Chief Editor's Notice . . . . . . . . . 1
Roberto Tamassia Guest Editor's Foreword . . . . . . . . 3
Julien Basch and
Harish Devarajan and
Piotr Indyk and
Li Zhang Probabilistic Analysis for Discrete
Attributes of Moving Points . . . . . . 5
Konstantinos G. Kakoulis and
Ioannis G. Tollis A Unified Approach to Automatic Label
Placement . . . . . . . . . . . . . . . 23
Jonathan Cohen and
Dinesh Manocha and
Marc Olano Successive Mappings: An Approach to
Polygonal Mesh Simplification with
Guaranteed Error Bounds . . . . . . . . 61
Danny Z. Chen and
Ovidiu Daescu Space-Efficient Algorithms for
Approximating Polygonal Curves in
Two-Dimensional Space . . . . . . . . . 95
Jerôme Galtier and
Ferran Hurtado and
Marc Noy and
Stéphane Pérennes and
Jorge Urrutia Simultaneous Edge Flipping in
Triangulations . . . . . . . . . . . . . 113
Danny Z. Chen and
Shuang Luan and
Jinhui Xu Topological Peeling and Applications . . 135
Eugene Fink and
Derick Wood Planar Strong Visibility . . . . . . . . 173
Jean-Daniel Boissonnat and
Sylvain Lazard A Polynomial-Time Algorithm for
Computing Shortest Paths of Bounded
Curvature Amidst Moderate Obstacles . . 189
Olivier Devillers and
Franco P. Preparata Culling a Set of Points for Roundness or
Cylindricity Evaluations . . . . . . . . 231
Kurt Mehlhorn and
Michael Seel Infimaximal Frames: a Technique for
Making Lines Look Like Segments . . . . 241
Asish Mukhopadhyay and
S. V. Rao On Computing a Largest Empty Arbitrarily
Oriented Rectangle . . . . . . . . . . . 257
Joseph O'Rourke Computational Geometry Column $ 44 $ . . 273
Kokichi Sugihara Guest Editor's Foreword . . . . . . . . 277
Marina L. Gavrilova and
Jon Rokne Collision Detection Optimization in a
Multi-Particle System . . . . . . . . . 279
Mattias Andersson and
Joachim Gudmundsson and
Christos Levcopoulos and
Giri Narasimhan Balanced Partition of Minimum Spanning
Trees . . . . . . . . . . . . . . . . . 303
J. M. Díaz-Báñez and
F. Hurtado and
H. Meijer and
D. Rappaport and
J. A. Sellar\`es The Largest Empty Annulus Problem . . . 317
Joachim Giesen and
Matthias John and
Michel Stöcklin Symmetry of Flow Diagrams Derived from
Weighted Points in the Plane . . . . . . 327
Maciej Dakowicz and
Christopher Gold Extracting Meaningful Slopes from
Terrain Contours . . . . . . . . . . . . 339
Chandrajit L. Bajaj and
Guoliang Xu and
Robert J. Holt and
Arun N. Netravali NURBS Approximation of $A$-splines and
$A$-patches . . . . . . . . . . . . . . 359
Olivier Devillers and
Regina Estkowski and
Pierre-Marie Gandoin and
Ferran Hurtado and
Pedro Ramos and
Vera Sacristán Minimal set of constraints for $2$ d
constrained Delaunay reconstruction . . 391
Tim Culver and
John Keyser and
Dinesh Manocha and
Shankar Krishnan A Hybrid Approach for Determinant Signs
of Moderate-Sized Matrices . . . . . . . 399
Sergei Bespamyatnikh Computing Closest Points for Segments 419
Peter Braß and
Laura Heinrich-Litan and
Pat Morin Computing the Center of Area of a Convex
Polygon . . . . . . . . . . . . . . . . 439
Prosenjit Bose and
Hazel Everett and
Stephen Wismath Properties of Arrangement Graphs . . . . 447
Chaim Linhart and
Dan Halperin and
Iddo Hanniel and
Sariel Har-Peled An Experimental Study of On-Line Methods
for Zone Construction in Arrangements of
Lines in the Plane . . . . . . . . . . . 463
Ashim Garg and
Adrian Rusu Area-Efficient Order-Preserving Planar
Straight-Line Drawings of Ordered Trees 487
Anonymous Author Index Volume 13 (2003) . . . . . 507
Binhai Zhu Guest Editor's Foreword . . . . . . . . 1
Sergey Bereg Cylindrical Hierarchy for Deforming
Necklaces . . . . . . . . . . . . . . . 3
Jinhui Xu and
Zhiyong Lin and
Yang Yang and
Ronald Berezney Traveling Salesman Problem of Segments 19
Ron Breukelaar and
Erik D. Demaine and
Susan Hohenberger and
Hendrik Jan Hoogeboom and
Walter A. Kosters and
David Liben-Nowell Tetris Is Hard, Even To Approximate . . 41
Xiang-Yang Li and
Yu Wang Efficient Construction of Low Weighted
Bounded Degree Planar Spanner . . . . . 69
Xiaodong Wu and
Danny Z. Chen and
James J. Mason and
Steven R. Schmid Efficient Approximation Algorithms for
Pairwise Data Clustering and
Applications . . . . . . . . . . . . . . 85
Michael J. Collins Covering a Set of Points with a Minimum
Number of Turns . . . . . . . . . . . . 105
Pascal Lienhardt and
Xavier Skapin and
Antoine Bergey Cartesian Product of Simplicial and
Cellular Structures . . . . . . . . . . 115
Ron Goldman and
Wenping Wang Using Invariants To Extract Geometric
Characteristics of Conic Sections From
Rational Quadratic Parameterizations . . 161
Binhai Zhu Approximating $3$D Points with
Cylindrical Segments . . . . . . . . . . 189
Matthew Suderman Pathwidth and Layered Drawings of Trees 203
Joseph O'Rourke Computational Geometry Column 45 . . . . 227
Joseph S. B. Mitchell Editor's Foreword . . . . . . . . . . . 231
Marc Van Kreveld and
Iris Reinbacher Good News: Partitioning a Simple Polygon
by Compass Directions . . . . . . . . . 233
Niloy J. Mitra and
An Nguyen and
Leonidas Guibas Estimating Surface Normals in Noisy
Point Cloud Data . . . . . . . . . . . . 261
Dan Halperin and
Eran Leiserowitz Controlled Perturbation for Arrangements
of Circles . . . . . . . . . . . . . . . 277
Danny Z. Chen and
Xiaobo S. Hu and
Shuang (Sean) Luan and
Chao Wang and
Xiaodong Wu Geometric Algorithms for Static Leaf
Sequencing Problems in Radiation Therapy 311
Kaspar Fischer and
Bernd Gärtner The Smallest Enclosing Ball of Balls:
Combinatorial Structure and Algorithms 341
Xiangmin Jiao and
Michael T. Heath Overlaying Surface Meshes, Part I:
Algorithms . . . . . . . . . . . . . . . 379
Xiangmin Jiao and
Michael T. Heath Overlaying Surface Meshes, Part II:
Topology Preservation and Feature
Matching . . . . . . . . . . . . . . . . 403
Evanthia Papadopoulou and
D. T. Lee The Hausdorff Voronoi Diagram of
Polygonal Objects: a Divide and Conquer
Approach . . . . . . . . . . . . . . . . 421
Hee-Kap Ahn and
Siu-Wing Cheng and
Otfried Cheong and
Jack Snoeyink The Reflex-Free Hull . . . . . . . . . . 453
Joseph O'Rourke Computational Geometry Column 46 . . . . 475
Anonymous Author Index Volume 14 (2004) . . . . . 479
Paul Chew and
Alper Üngör Guest Editors' Foreword . . . . . . . . 1
Daniel K. Blandford and
Guy E. Blelloch and
David E. Cardoze and
Clemens Kadow Compact Representations of Simplicial
Meshes in Two and Three Dimensions . . . 3
Gary L. Miller and
Steven E. Pav and
Noel J. Walkington When and Why Delaunay Refinement
Algorithms Work . . . . . . . . . . . . 25
Suneeta Ramaswami and
Marcelo Siqueira and
Tessa Sundaram and
Jean Gallier and
James Gee Constrained Quadrilateral Meshes of
Bounded Size . . . . . . . . . . . . . . 55
Marina L. Gavrilova Guest Editors' Foreword . . . . . . . . 99
Godfried Toussaint Geometric Proximity Graphs for Improving
Nearest Neighbor Methods in
Instance-Based Learning and Data Mining 101
Takeshi Kanda and
Kokichi Sugihara Two-Dimensional Range Search Based on
the Voronoi Diagram . . . . . . . . . . 151
Ferran Hurtado and
Carlos Seara and
Saurabh Sethia Red-Blue Separability Problems in $3$D 167
Sergey Bereg An Approximate Morphing Between
Polylines . . . . . . . . . . . . . . . 193
Donguk Kim and
Deok-Soo Kim and
Kokichi Sugihara Euclidean Voronoi Diagram for Circles in
a Circle . . . . . . . . . . . . . . . . 209
Atsushi Kaneko and
Mikio Kano Semi-Balanced Partitions of Two Sets of
Points and Embeddings of Rooted Forests 229
Danny Z. Chen and
Michiel Smid and
Bin Xu Geometric Algorithms for Density-Based
Data Clustering . . . . . . . . . . . . 239
Yu-Shin Chen and
D. T. Lee and
Chung-Shou Liao Labeling Points on a Single Line . . . . 261
Hilderick A. Van Der Meiden and
Willem F. Bronsvoort An Efficient Method to Determine the
Intended Solution for a System of
Geometric Constraints . . . . . . . . . 279
Huawei Wang and
Kaihuai Qin and
Hanqiu Sun Evaluation of Non-Uniform Doo--Sabin
Surfaces . . . . . . . . . . . . . . . . 299
Gill Barequet Guest Editor's Foreword . . . . . . . . 325
Ilya Baran and
Erik D. Demaine Optimal Adaptive Algorithms for Finding
the Nearest and Farthest Point on a
Parametric Black-Box Curve . . . . . . . 327
Ron Wein and
Oleg Ilushin and
Gershon Elber and
Dan Halperin Continuous Path Verification in
Multi-Axis NC-Machining . . . . . . . . 351
Stefan Funke and
Theocharis Malamatos and
Rahul Ray Finding planar regions in a terrain --
in practice and with a guarantee . . . . 379
Erik D. Demaine and
Jeff Erickson and
Ferran Hurtado and
John Iacono and
Stefan Langerman and
Henk Meijer and
Mark Overmars and
Sue Whitesides Separating Point Sets in Polygonal
Environments . . . . . . . . . . . . . . 403
Siu-Wing Cheng and
Tamal K. Dey and
Edgar A. Ramos and
Tathagata Ray Quality Meshing of Polyhedra with Small
Angles . . . . . . . . . . . . . . . . . 421
Frank Dehne and
Rolf Klein and
Raimund Seidel Maximizing a Voronoi Region: the Convex
Case . . . . . . . . . . . . . . . . . . 463
Abedallah Rababah $ L_2 $ Degree Reduction of Triangular
Bézier Surfaces with Common Tangent
Planes At Vertices . . . . . . . . . . . 477
Sumanta Guha Joint Separation of Geometric Clusters
and the Extreme Irregularities of
Regular Polyhedra . . . . . . . . . . . 491
Frédéic Cazals and
Marc Pouget Differential Topology and Geometry of
Smooth Embedded Surfaces: Selected
Topics . . . . . . . . . . . . . . . . . 511
Peter Brass and
Mehrbod Sharifi A Lower Bound for Lebesgue's Universal
Cover Problem . . . . . . . . . . . . . 537
Henk Meijer and
David Rappaport Guest Editors' Foreword . . . . . . . . 545
Daniel Archambault and
Willam Evans and
David Kirkpatrick Computing the Set of All the Distant
Horizons of a Terrain . . . . . . . . . 547
Sean M. Falconer and
Bradford G. Nickerson On Multi-Level $k$-Ranges for Range
Search . . . . . . . . . . . . . . . . . 565
Gruia C\ualinescu and
Adrian Dumitrescu and
Howard Karloff and
Peng-Jun Wan Separating Points by Axis-Parallel Lines 575
Prosenjit Bose and
Marc Van Kreveld Generalizing Monotonicity: on
Recognizing Special Classes of Polygons
and Polyhedra . . . . . . . . . . . . . 591
Amit M. Bhosle and
Teofilo F. Gonzalez Exact and Approximation Algorithms for
Finding an Optimal Bridge Connecting Two
Simple Polygons . . . . . . . . . . . . 609
Anonymous Author Index Volume 15 (2005) . . . . . 631
Esther M. Arkin and
Ferran Hurtado and
Joseph S. B. Mitchell and
Carlos Seara and
Steven S. Skiena Some Lower Bounds on Geometric
Separability Problems . . . . . . . . . 1
Dominique Michelucci and
Sebti Foufou Interval-Based Tracing of Strange
Attractors . . . . . . . . . . . . . . . 27
Kai Tang and
Charlie C. L. Wang and
Danny Z. Chen Minimum Area Convex Packing of Two
Convex Polygons . . . . . . . . . . . . 41
Guoliang Xu Discrete Laplace--Beltrami Operator on
Sphere and Optimal Spherical
Triangulations . . . . . . . . . . . . . 75
Rudolf Fleischer Guest Editor's Foreword . . . . . . . . 95
Boris Aronov and
Tetsuo Asano and
Naoki Katoh and
Kurt Mehlhorn and
Takeshi Tokuyama Polyline Fitting of Planar Points Under
Min-Sum Criteria . . . . . . . . . . . . 97
Sang Won Bae and
Kyung-Yong Chwa Voronoi Diagrams for a Transportation
Network on the Euclidean Plane . . . . . 117
Timothy M. Chan and
Bashir S. Sadjad Geometric Optimization Problems Over
Sliding Windows . . . . . . . . . . . . 145
Chao Chen and
Ho-Lun Cheng Superimposing Voronoi Complexes for
Shape Deformation . . . . . . . . . . . 159
Danny Z. Chen and
Xiaobo X. Hu and
Shuang Luan and
Shahid A. Naqvi and
Chao Wang and
Cedric X. Yu Generalized Geometric Approaches for
Leaf Sequencing Problems in Radiation
Therapy . . . . . . . . . . . . . . . . 175
Kyung-Yong Chwa and
Byung-Cheol Jo and
Christian Knauer and
Esther Moet and
René Van Oostrum and
Chan-Su Shin Guarding Art Galleries by Guarding
Witnesses . . . . . . . . . . . . . . . 205
Ovidiu Daescu and
Jun Luo Cutting Out Polygons with Lines and Rays 227
Kazuyuki Miura and
Hiroki Haga and
Takao Nishizeki Inner Rectangular Drawings of Plane
Graphs . . . . . . . . . . . . . . . . . 249
Richard J. Nowakowski and
Norbert Zeh Boundary-Optimal Triangulation Flooding 271
Erik Carlsson and
Gunnar Carlsson and
Vin De Silva An Algebraic Topological Method for
Feature Identification . . . . . . . . . 291
J. M. Díaz-Báñez and
F. Gómez and
I. Ventura The Anchored Voronoi Diagram: Static,
Dynamic Versions and Applications . . . 315
Moshe Dror and
Yusin Lee and
James B. Orlin and
Valentin Polishchuk The TSP and the Sum of Its Marginal
Values . . . . . . . . . . . . . . . . . 333
Stephane Durocher and
David Kirkpatrick The Steiner Centre of a Set of Points:
Stability, Eccentricity, and
Applications to Mobile Facility Location 345
Joseph O'Rourke Computational Geometry Column 47 . . . . 373
Xiao-Shan Gao and
Dominique Michelucci Guest Editors' Foreword . . . . . . . . 377
Christophe Jermann and
Gilles Trombettoni and
Bertrand Neveu and
Pascal Mathis Decomposition of Geometric Constraint
Systems: a Survey . . . . . . . . . . . 379
Bill Jackson and
Tibor Jordán On the Rank Function of the
$3$-Dimensional Rigidity Matroid . . . . 415
Pascal Schreck and
Pascal Mathis Geometrical Constraint System
Decomposition: a Multi-Group Approach 431
Dominique Michelucci and
Pascal Schreck Incidence Constraints: a Combinatorial
Approach . . . . . . . . . . . . . . . . 443
Gui-Fang Zhang and
Xiao-Shan Gao Well-Constrained Completion and
Decomposition for Under-Constrained
Geometric Constraint Problems . . . . . 461
Gilles Trombettoni and
Marta Wilczkowiak GPDOF --- a Fast Algorithm to Decompose
Under-Constrained Geometric Constraint
Systems: Application to $3$D Modeling 479
Ming Zhang and
Liqun Wang and
Ronald Goldman Bézier Subdivision for Inverse Molecular
Kinematics . . . . . . . . . . . . . . . 513
Lu Yang Solving Spatial Constraints with Global
Distance Coordinate System . . . . . . . 533
Philippe Serré and
Auxkin Ortuzar and
Alain Rivi\`ere Non-Cartesian Modelling for Analysis of
the Consistency of a Geometric
Specification for Conceptual Design . . 549
Ee-Chien Chang and
Sung Woo Choi and
Do Yong Kwon and
Hyungju Park and
Chee K. Yap Shortest Path Amidst Disc Obstacles Is
Computable . . . . . . . . . . . . . . . 567
Meera Sitharam Well-Formed Systems of Point Incidences
for Resolving Collections of Rigid
Bodies . . . . . . . . . . . . . . . . . 591
Anonymous Author Index Volume 16 (2006) . . . . . 617
Daniel A. Spielman and
Shang-Hua Teng and
Alper Üngör Parallel Delaunay Refinement: Algorithms
and Analyses . . . . . . . . . . . . . . 1--30
Mireille Boutin and
Gregor Kemper Which Point Configurations Are
Determined by the Distribution of Their
Pairwise Distances? . . . . . . . . . . 31--43
Jae-Sook Cheong and
A. Frank Van Der Stappen and
Ken Goldberg and
Mark H. Overmars and
Elon Rimon Immobilizing Hinged Polygons . . . . . . 45--69
Nargess Memarsadeghi and
David M. Mount and
Nathan S. Netanyahu and
Jacqueline Le Moigne A Fast Implementation of the ISODATA
Clustering Algorithm . . . . . . . . . . 71--103
Chris Worman and
J. Mark Keil Polygon Decomposition and the Orthogonal
Art Gallery Problem . . . . . . . . . . 105--138
Emilio Di Giacomo and
Giuseppe Liotta Simultaneous Embedding of Outerplanar
Graphs, Paths, and Cycles . . . . . . . 139--160
Stefan Kirchner An FPTAS for Computing the Similarity of
Three-Dimensional Point Sets . . . . . . 161--174
Victor Milenkovic and
Elisha Sacks An Approximate Arrangement Algorithm for
Semi-Algebraic Curves . . . . . . . . . 175--198
Li Zhang Guest Editor's Foreword . . . . . . . . 199--200
Annette Ebbers-Baumann and
Ansgar Grüne and
Rolf Klein and
Marek Karpinski and
Christian Knauer and
Andrzej Lingas Embedding Point Sets into Plane Graphs
of Small Dilation . . . . . . . . . . . 201--230
Matthias Müller-Hannemann and
Anna Schulze Hardness and Approximation of Octilinear
Steiner Trees . . . . . . . . . . . . . 231--260
Xiaodong Wu and
Danny Z. Chen and
Kang Li and
Milan Sonka The Layered Net Surface Problems in
Discrete Geometry and Medical Image
Segmentation . . . . . . . . . . . . . . 261--296
Olivier Devillers and
Vida Dujmovi\'c and
Hazel Everett and
Samuel Hornus and
Sue Whitesides and
Steve Wismath Maintaining Visibility Information of
Planar Point Sets with a Moving
Viewpoint . . . . . . . . . . . . . . . 297--304
Sahand Jamal Rahi and
Kim Sharp Mapping Complicated Surfaces Onto a
Sphere . . . . . . . . . . . . . . . . . 305--329
Esther Moet and
Marc Van Kreveld and
René Van Oostrum Region Intervisibility in Terrains . . . 331--347
Otfried Cheong and
Hazel Everett and
Hyo-Sil Kim and
Sylvain Lazard and
René Schott Parabola Separation Queries and Their
Application to Stone Throwing . . . . . 349--360
Hazel Everett and
Sylvain Lazard and
Sylvain Petitjean and
Linqiao Zhang On the Expected Size of the $2$D
Visibility Complex . . . . . . . . . . . 361--381
Victor Milenkovic and
Elisha Sacks A Monotonic Convolution for Minkowski
Sums . . . . . . . . . . . . . . . . . . 383--396
Joseph O'Rourke Computational Geometry Column 48 . . . . 397--399
Leif Kobbelt and
Vadim Shapiro Guest Editor's Foreword . . . . . . . . 401--402
Frederic Chazal and
Andre Lieutier and
Jarek Rossignac Normal-Map Between Normal-Compatible
Manifolds . . . . . . . . . . . . . . . 403--421
Avneesh Sud and
Mark Foskey and
Dinesh Manocha Homotopy-Preserving Medial Axis
Simplification . . . . . . . . . . . . . 423--451
I. Hanniel and
M. Ramanathan and
G. Elber and
M.-S. Kim Precise Voronoi Cell Extraction of
Free-Form Planar Piecewise $ C^1
$-Continuous Closed Rational Curves . . 453--486
Jason Williams and
Jarek Rossignac Tightening: Morphological Simplification 487--503
Friedrich Eisenbrand and
Stefan Funke and
Andreas Karrenbauer and
Joachim Reichel and
Elmar Schömer Packing a Truck --- Now With a Twist! 505--527
Prosenjit Bose and
Narcís Coll and
Ferran Hurtado and
J. Antoni Sellar\`es A General Approximation Algorithm for
Planar Maps with Applications . . . . . 529--554
Paul Harrington and
Colm Ó. Dúnlaing and
Chee K. Yap Optimal Voronoi Diagram Construction
With n Convex Sites In Three Dimensions 555--593
F. Betul Atalay and
David M. Mount Pointerless Implementation of
Hierarchical Simplicial Meshes and
Efficient Neighbor Finding in Arbitrary
Dimensions . . . . . . . . . . . . . . . 595--631
Anonymous Author Index Volume 17 (2007) . . . . . 633--635
Alon Efrat Guest Editor's Foreword . . . . . . . . 1--2
Gereon Frahling and
Piotr Indyk and
Christian Sohler Sampling in Dynamic Data Streams and
Applications . . . . . . . . . . . . . . 3--28
Tamal K. Dey and
Joachim Giesen and
Edgar A. Ramos and
Bardia Sadri Critical Points of Distance to an $
\epsilon $-Sampling of a Surface and
Flow-Complex-Based Surface
Reconstruction . . . . . . . . . . . . . 29--61
Danny Z. Chen and
Xiaobo S. Hu and
Chao Wang and
Shuang Luan and
Xiaodong Wu Mountain Reduction, Block Matching, and
Applications in Intensity-Modulated
Radiation Therapy . . . . . . . . . . . 63--106
Friedrich Eisenbrand and
Stefan Funke and
Andreas Karrenbauer and
Domagoj Matijevic Energy-Aware Stage Illumination . . . . 107--129
David Eppstein and
Michael T. Goodrich and
Jonathan Z. Sun Skip Quadtrees: Dynamic Data Structures
for Multidimensional Point Sets . . . . 131--160
Stephane Durocher and
David Kirkpatrick Bounded-Velocity Approximation of Mobile
Euclidean 2-Centres . . . . . . . . . . 161--183
Magdalene Grantson Borgelt and
Christian Borgelt and
Christos Levcopoulos Fixed Parameter Algorithms for the
Minimum Weight Triangulation Problem . . 185--220
Martin Heimlich and
Martin Held Biarc Approximation, Simplification and
Smoothing of Polygonal Curves by Means
of Voronoi-Based Tolerance Bands . . . . 221--250
Fabrizio Frati On Minimum Area Planar Upward Drawings
of Directed Trees and Other Families of
Directed Acyclic Graphs . . . . . . . . 251--271
Kokichi Sugihara and
Deok-Soo Kim Guest Editors' Foreword . . . . . . . . 273--274
Robert Görke and
Chan-Su Shin and
Alexander Wolff Constructing the City Voronoi Diagram
Faster . . . . . . . . . . . . . . . . . 275--294
Manuel Abellanas and
Ferran Hurtado and
Belén Palop The Heavy Luggage Metric . . . . . . . . 295--306
Helmut Alt and
Ludmila Scharf Computing the Hausdorff Distance Between
Curved Objects . . . . . . . . . . . . . 307--320
Hisamoto Hiyoshi Stable Computation of Natural Neighbor
Interpolation . . . . . . . . . . . . . 321--341
Yuanxin Liu and
Jack Snoeyink Faraway Point: a Sentinel Point for
Delaunay Computation . . . . . . . . . . 343--355
Hayong Shin and
Seyoun Park and
Eonjin Park and
Deok-Soo Kim Voronoi Diagram of a Polygon in
Chessboard Metric and Maskless
Lithographic Applications . . . . . . . 357--371
Sergey Bereg and
Adrian Dumitrescu and
János Pach Sliding Disks in the Plane . . . . . . . 373--387
Bin Fu and
Sorinel A. Oprisan and
Lizhe Xu Multi-Directional Width-Bounded
Geometric Separator and Protein Folding 389--413
Siu-Wing Cheng and
Yajun Wang and
Zhuangzhi Wu Provable Dimension Detection Using
Principal Component Analysis . . . . . . 415--440
Giorgio Scorzelli and
Alberto Paoluzzi and
Valerio Pascucci Parallel Solid Modeling Using BSP
Dataflow . . . . . . . . . . . . . . . . 441--467
Gill Barequet and
Aya Steiner On the Matability of Polygons . . . . . 469--506
Nina Amenta and
Otfried Cheong Guest Editors' Foreword . . . . . . . . 507--508
François Labelle Sliver Removal by Lattice Refinement . . 509--532
Joachim Giesen and
Edgar A. Ramos and
Bardia Sadri Medial Axis Approximation and Unstable
Flow Complex . . . . . . . . . . . . . . 533--565
Ioannis Z. Emiris and
Elias P. Tsigaridas and
George M. Tzoumas The Predicates for the Exact Voronoi
Diagram of Ellipses Under the Euclidean
Metric . . . . . . . . . . . . . . . . . 567--597
Noga Alon and
Shakhar Smorodinsky Conflict-Free Colorings of Shallow Discs 599--604
Gereon Frahling and
Christian Sohler A Fast $k$-Means Implementation Using
Coresets . . . . . . . . . . . . . . . . 605--625
Anonymous Author Index Volume 18 (2008) . . . . . 627--629
Tetsuo Asano Guest Editor's Foreword . . . . . . . . 93--93
Sang Won Bae and
Jae-Hoon Kim and
Kyung-Yong Chwa Optimal Construction of the City Voronoi
Diagram . . . . . . . . . . . . . . . . 95--117
Prosenjit Bose and
Michiel Smid and
Daming Xu Delaunay and Diamond Triangulations
Contain Spanners of Bounded Degree . . . 119--140
Xiaodong Wu Efficient Algorithms for the
Optimal-Ratio Region Detection Problems
in Discrete Geometry with Applications 141--159
Yusu Wang Relations Between Two Common Types of
Rectangular Tilings . . . . . . . . . . 161--172
Khaled Elbassioni and
Aleksei V. Fishkin and
René Sitters Approximation Algorithms for the
Euclidean Traveling Salesman Problem
with Discrete and Continuous
Neighborhoods . . . . . . . . . . . . . 173--193
Scott E. Dillard and
Vijay Natarajan and
Gunther H. Weber and
Valerio Pascucci and
Bernd Hamann Topology-Guided Tessellation Of
Quadratic Elements . . . . . . . . . . . 195--211
Danny Z. Chen and
D. T. Lee Editors' Foreword . . . . . . . . . . . 213--214
Gadi Aleksandrowicz and
Gill Barequet Counting $d$-Dimensional Polycubes and
Nonrectangular Planar Polyominoes . . . 215--229
Xiaodong Wu and
Xin Dou and
John E. Bayouth and
John M. Buatti Efficient Algorithm for Optimal Matrix
Orthogonal Decomposition Problem in
Intensity-Modulated Radiation Therapy 231--246
Mattias Andersson and
Joachim Gudmundsson and
Christos Levcopoulos Restricted Mesh Simplification Using
Edge Contractions . . . . . . . . . . . 247--265
Marc Benkert and
Joachim Gudmundsson and
Christian Knauer and
René Van Oostrum and
Alexander Wolff A Polynomial-Time Approximation
Algorithm for a Geometric Dispersion
Problem . . . . . . . . . . . . . . . . 267--288
Sheung-Hung Poon On Unfolding Lattice Polygons/Trees and
Diameter-4 Trees . . . . . . . . . . . . 289--321
Jon Rokne Guest Editor's Foreword . . . . . . . . 323--324
Stefan Porschen On Rectangular Covering Problems . . . . 325--340
Marina L. Gavrilova Determining a Set of Maximum Inscribed
Rectangles for Label Placement in a
Region . . . . . . . . . . . . . . . . . 341--356
Debabrata Bardhan and
Sansanka Roy and
Sandip Das Guard Placement for Maximizing
$L$-Visibility Exterior to a Convex
Polygon . . . . . . . . . . . . . . . . 357--370
D. Jiang and
N. F. Stewart Floating-Point Arithmetic for
Computational Geometry Problems with
Uncertain Data . . . . . . . . . . . . . 371--385
Deok-Soo Kim Guest Editor's Foreword . . . . . . . . 387--388
Frank Nielsen and
Richard Nock Approximating Smallest Enclosing Balls
with Applications to Machine Learning 389--414
Marina L. Gavrilova An Explicit Solution for Computing the
Vertices of the Euclidean
$d$-Dimensional Voronoi Diagram of
Spheres in a Floating-Point Arithmetic 415--424
Tetsushi Nishida and
Kokichi Sugihara Boat-Sail Voronoi Diagram and Its
Application . . . . . . . . . . . . . . 425--440
Henk Bekker and
Axel A. Brink and
Jos B. T. M. Roerdink Reducing the Time Complexity and
Identifying Ill-Posed Problem Instances
of Minkowski Sum Based Similarity
Calculations . . . . . . . . . . . . . . 441--456
Sandip Das and
Partha P. Goswami and
Subhas C. Nandy Smallest Color-Spanning Object Revisited 457--478
Prosenjit Gupta and
Ravi Janardan and
Michiel Smid Efficient Non-Intersection Queries on
Aggregated Geometric Data . . . . . . . 479--506
Jean Cardinal and
Martine Labbé and
Stefan Langerman and
Belén Palop Pricing Geometric Transportation
Networks . . . . . . . . . . . . . . . . 507--520
C. J. Sangwin Deceiving the $V$-Block Method for
Assessment of Departure from Roundness 521--532
Sergio Cabello and
Mark De Berg and
Panos Giannopoulos and
Christian Knauer and
René Van Oostrum and
Remco C. Veltkamp Maximizing the Area of Overlap of Two
Unions of Disks Under Rigid Motion . . . 533--556
Asish Mukhopadhyay and
Eugene Greene and
S. V. Rao On Intersecting a Set of Isothetic Line
Segments with a Convex Polygon of
Minimum Area . . . . . . . . . . . . . . 557--577
Yefim Dinitz and
Matthew J. Katz and
Roi Krakovski Guarding Rectangular Partitions . . . . 579--594
Manuel Abellanas and
Prosenjit Bose and
Jesús García and
Ferran Hurtado and
Carlos M. Nicolás and
Pedro Ramos On Structural and Graph Theoretic
Properties of Higher Order Delaunay
Graphs . . . . . . . . . . . . . . . . . 595--615
Anonymous Author Index Volume 19 (2009) . . . . . 617--619
Takeshi Tokuyama Foreword . . . . . . . . . . . . . . . . 1--2
Eric Y. Chen Geometric Streaming Algorithm with a
Sorting Primitive . . . . . . . . . . . 3--18
Marc Benkert and
Bojan Djordjevic and
Joachim Gudmundsson and
Thomas Wolle Finding Popular Places . . . . . . . . . 19--42
Jinhui Xu and
Yang Yang and
Yongding Zhu and
Naoki Katoh A Geometric Spanner of Segments . . . . 43--67
Hee-Kap Ahn and
Mohammad Farshi and
Christian Knauer and
Michiel Smid and
Yajun Wang Dilation-Optimal Edge Deletion in
Polygonal Cycles . . . . . . . . . . . . 69--87
Boris Aronov and
Tetsuo Asano and
Stefan Funke Optimal Triangulations of Points and
Segments with Steiner Points . . . . . . 89--104
Sergey Bereg and
Adrian Dumitrescu and
Minghui Jiang Maximum Area Independent Sets in Disk
Intersection Graphs . . . . . . . . . . 105--118
Pengpeng Wang and
Ramesh Krishnamurti and
Kamal Gupta Generalized Watchman Route Problem with
Discrete View Cost . . . . . . . . . . . 119--146
Panos Giannopoulos and
Rolf Klein and
Christian Knauer and
Martin Kutz and
Dániel Marx Computing Geometric Minimum-Dilation
Graphs Is NP-Hard . . . . . . . . . . . 147--173
Tsunehiko Kameda and
John Z. Zhang Finding All Door Locations That Make a
Room Searchable . . . . . . . . . . . . 175--201
Mark De Berg and
Elena Mumford and
Bettina Speckmann Optimal BSPs and Rectilinear Cartograms 203--222
Andrzej \.Zak Dissections of Polygons into Convex
Polygons . . . . . . . . . . . . . . . . 223--244
Erik D. Demaine and
John Iacono and
Stefan Langerman Grid Vertex-Unfolding Orthostacks . . . 245--254
Yoav Gabriely and
Elon Rimon Competitive Complexity of Mobile Robot
On-Line Motion Planning Problems . . . . 255--283
Frédéric Chazal and
André Lieutier and
Jarek Rossignac and
Brian Whited Ball-Map: Homeomorphism Between
Compatible Surfaces . . . . . . . . . . 285--306
Tom Kamphans and
Elmar Langetepe Leaving an Unknown Maze Using an
Error-Prone Compass . . . . . . . . . . 307--325
Peter Brass and
Hyeon-Suk Na and
Chan-Su Shin Guarding a Polygon from Two
Nearly-Opposite Directions . . . . . . . 327--339
Peter Brass and
Ferran Hurtado and
Benjamin Lafreniere and
Anna Lubiw A Lower Bound on the Area of a
3-Coloured Disk Packing . . . . . . . . 341--360
Rodrigo I. Silveira and
René Van Oostrum Flooding Countries and Destroying Dams 361--380
Chris Gray and
Maarten Löffler and
Rodrigo I. Silveira Smoothing Imprecise $ 1.5 $D Terrains 381--414
Sanjiv Kapoor and
Xiang-Yang Li Proximity Structures for Geometric
Graphs . . . . . . . . . . . . . . . . . 415--429
Pankaj Kumar and
Piyush Kumar Almost Optimal Solutions To
$k$-Clustering Problems . . . . . . . . 431--447
Danny Z. Chen and
Ewa Misio\lek Finding Many Optimal Paths Without
Growing Any Optimal Path Trees . . . . . 449--469
Sergey Bereg and
Kevin Buchin and
Maike Buchin and
Marina Gavrilova and
Binhai Zhu Voronoi Diagram of Polygonal Chains
Under the Discrete Fréchet Distance . . . 471--484
Victor Milenkovic and
Elisha Sacks Two Approximate Minkowski Sum Algorithms 485--509
Andrea Anghinolfi and
Luca Costa and
Massimo Ferri and
Enrico Viarani A Covering Projection for Robot
Navigation Under Strong Anisotropy . . . 511--525
M. Kano and
Miyuki Uno Balanced Subdivisions with Boundary
Condition of Two Sets of Points in the
Plane . . . . . . . . . . . . . . . . . 527--541
Ranjith Unnikrishnan and
Jean-François Lalonde and
Nicolas Vandapel and
Martial Hebert Scale Selection for Geometric Fitting in
Noisy Point Clouds . . . . . . . . . . . 543--575
Emilio Di Giacomo and
Walter Didimo and
Giuseppe Liotta and
Henk Meijer and
Stephen K. Wismath Constrained Point-Set Embeddability of
Planar Graphs . . . . . . . . . . . . . 577--600
Yoav Amit and
Joseph S. B. Mitchell and
Eli Packer Locating Guards for Visibility Coverage
of Polygons . . . . . . . . . . . . . . 601--630
Meera Sitharam and
Yong Zhou and
Jörg Peters Reconciling Conflicting Combinatorial
Preprocessors for Geometric Constraint
Systems . . . . . . . . . . . . . . . . 631--651
Josh Brown Kramer and
Lucas Sabalka Multidimensional Online Motion Planning
for a Spherical Robot . . . . . . . . . 653--684
Bill Jackson and
Tibor Jordán Operations Preserving Global Rigidity of
Generic Direction-Length Frameworks . . 685--706
Victor Chepoi and
Karim Nouioua and
Edouard Thiel and
Yann Vax\`es Pareto Envelopes in Simple Polygons . . 707--721
J. C. Owen and
S. C. Power Frameworks Symmetry and Rigidity . . . . 723--750
Anonymous Author Index Volume 20 (2010) . . . . . 751--754
Maarten Löffler Existence and Computation of Tours
Through Imprecise Points . . . . . . . . 1--24
Prosenjit Bose and
Merc\`e Mora and
Carlos Seara and
Saurabh Sethia On Computing Enclosing Isosceles
Triangles and Related Problems . . . . . 25--45
Oswin Aichholzer and
Franz Aurenhammer and
Thomas Hackl and
Bert Jüttler and
Margot Rabl and
Zbynek \vSír Computational and Structural Advantages
of Circular Boundary Representation . . 47--69
Md. Ashraful Alam and
Masud Hasan Computing Nice Projections of Convex
Polyhedra . . . . . . . . . . . . . . . 71--85
Greg Aloupis and
Prosenjit Bose and
Erik D. Demaine and
Stefan Langerman and
Henk Meijer and
Mark Overmars and
Godfried T. Toussaint Computing Signed Permutations of
Polygons . . . . . . . . . . . . . . . . 87--100
Karl J. Obermeyer and
Anurag Ganguli and
Francesco Bullo A Complete Algorithm for Searchlight
Scheduling . . . . . . . . . . . . . . . 101--130
John Reif and
Sam Slee Asymptotically Optimal Kinodynamic
Motion Planning for a Class of Modular
Self-Reconfigurable Robots . . . . . . . 131--155
Peter Brass and
Christian Knauer and
Hyeon-Suk Na and
Chan-Su Shin and
Antoine Vigneron The Aligned $K$-Center Problem . . . . . 157--178
Otfried Cheong and
Antoine Vigneron and
Juyoung Yon Reverse Nearest Neighbor Queries in
Fixed Dimension . . . . . . . . . . . . 179--188
Vladimir Estivill-Castro and
Apichat Heednacram and
Francis Suraweera FPT-Algorithms for Minimum-Bends Tours 189--213
Therese Biedl and
Masud Hasan and
Alejandro López-Ortiz Reconstructing Convex Polygons and
Convex Polyhedra from Edge and Face
Counts in Orthogonal Projections . . . . 215--239
Matthew J. Katz and
Gila Morgenstern Guarding Orthogonal Art Galleries with
Sliding Cameras . . . . . . . . . . . . 241--250
Seok-Hee Hong and
Hiroshi Nagamochi Guest Editors' Foreword . . . . . . . . 251--252
Kevin Buchin and
Maike Buchin and
Joachim Gudmundsson and
Maarten Löffler and
Jun Luo Detecting Commuting Patterns by
Clustering Subtrajectories . . . . . . . 253--282
Cheng-Wei Luo and
Hsiao-Fei Liu and
Peng-An Chen and
Kun-Mao Chao Minkowski Sum Selection and Finding . . 283--311
Sang-Sub Kim and
Sang Won Bae and
Hee-Kap Ahn Covering a Point Set by Two Disjoint
Rectangles . . . . . . . . . . . . . . . 313--330
Zeyu Guo and
He Sun and
Hong Zhu Greedy Construction of 2-Approximate
Minimum Manhattan Networks . . . . . . . 331--350
Ludmila Scharf and
Marc Scherfenberg Inducing Polygons of Line Arrangements 351--368
Christian Knauer and
Marc Scherfenberg Approximate Nearest Neighbor Search
Under Translation Invariant Hausdorff
Distance . . . . . . . . . . . . . . . . 369--381
Therese Biedl and
Burkay Genç Stoker's Theorem for Orthogonal
Polyhedra . . . . . . . . . . . . . . . 383--391
Luca Castelli Aleardi and
Olivier Devillers and
Abdelkrim Mebarki Catalog-Based Representation of $2$D
Triangulations . . . . . . . . . . . . . 393--402
Guillaume Batog and
Xavier Goaoc Inflating Balls is NP-Hard . . . . . . . 403--415
Chansophea Chuon and
Sumanta Guha and
Paul Janecek and
Nguyen Duc Cong Song Simplipoly: Curvature-Based Polygonal
Curve Simplification . . . . . . . . . . 417--429
Mustaq Ahmed and
Anna Lubiw Shortest Descending Paths: Towards an
Exact Algorithm . . . . . . . . . . . . 431--466
Thiago R. Dos Santos and
Hans-Peter Meinzer and
Lena Maier-Hein Extending the Doubly Linked Face List
for the Representation of
2-Pseudomanifolds and 2-Manifolds with
Boundaries . . . . . . . . . . . . . . . 467--494
Khaled Elbassioni and
Amr Elmasry and
Kazuhisa Makino Finding Simplices Containing the Origin
in Two and Three Dimensions . . . . . . 495--506
Alexander Rand and
Noel Walkington Delaunay Refinement Algorithms for
Estimating Local Feature Size in $2$D
and $3$D . . . . . . . . . . . . . . . . 507--543
A. M. Berkoff and
J. M. Henle and
A. E. Mcdonough and
A. P. Wesolowski Possibilities and Impossibilities in
Square-Tiling . . . . . . . . . . . . . 545--558
Guilherme D. Da Fonseca Fitting Flats to Points with Outliers 559--569
Serge Gosselin and
Carl Ollivier-Gooch Constructing Constrained Delaunay
Tetrahedralizations of Volumes Bounded
by Piecewise Smooth Surfaces . . . . . . 571--594
Magdalene G. Borgelt and
Marc Van Kreveld and
Jun Luo Geodesic Disks and Clustering in a
Simple Polygon . . . . . . . . . . . . . 595--608
Danny Z. Chen and
Ewa Misio\lek Free-Form Surface Partition in $3$-D . . 609--634
Wael El Oraiby and
Dominique Schmitt and
Jean-Claude Spehner Centroid Triangulations From $k$-Sets 635--659
Hirofumi Aota and
Takuro Fukunaga and
Hiroshi Nagamochi An Approximation Algorithm for Locating
Maximal Disks Within Convex Polygons . . 661--684
A. Karim Abu-Affash and
Paz Carmi and
Matthew J. Katz and
Gila Morgenstern Multi Cover of a Polygon Minimizing the
Sum of Areas . . . . . . . . . . . . . . 685--698
Anonymous Author Index Volume 21 (2011) . . . . . 699--702
Otfried Cheong and
Yoshio Okamoto Guest Editors' Foreword . . . . . . . . 1
Sang Won Bae and
Chan-Su Shin The Onion Diagram: a Voronoi-Like
Tessellation of a Planar Line Space and
Its Applications . . . . . . . . . . . . 3
Hee-Kap Ahn and
Christian Knauer and
Marc Scherfenberg and
Lena Schlipf and
Antoine Vigneron Computing the Discrete Fréchet Distance
with Imprecise Input . . . . . . . . . . 27
Christian Wulff-Nilsen and
Ansgar Grüne and
Rolf Klein and
Elmar Langetepe and
D. T. Lee and
Tien-Ching Lin and
Sheung-Hung Poon and
Teng-Kai Yu Computing the Stretch Factor and Maximum
Detour of Paths, Trees, and Cycles in
the Normed Space . . . . . . . . . . . . 45
Prosenjit Bose and
Mirela Damian and
Karim Douïeb and
Joseph O'Rourke and
Ben Seamone and
Michiel Smid and
Stefanie Wuhrer $ \pi / 2 $-Angle Yao graphs Are
Spanners . . . . . . . . . . . . . . . . 61
Siu-Wing Cheng and
Jiongxin Jin and
Antoine Vigneron and
Yajun Wang Approximate Shortest Homotopic Paths in
Weighted Regions . . . . . . . . . . . . 83
Andrzej Lingas and
Agnieszka Wasylewicz and
Pawe\l \.Zyli\'nski Linear-Time $3$-Approximation Algorithm
for the $r$-Star Covering Problem . . . 103
Esther M. Arkin and
Delia Garijo and
Alberto Márquez and
Joseph S. B. Mitchell and
Carlos Seara Separability of Point Sets by $k$-Level
Linear Classification Trees . . . . . . 143
Jan B. Zernisch A Generalization of a Theorem of
Kleitman and Krieger . . . . . . . . . . 167
Mark De Berg and
Amirali Khosravi Optimal Binary Space Partitions for
Segments in the Plane . . . . . . . . . 187
David Charlton and
Erik D. Demaine and
Martin L. Demaine and
Vida Dujmovi\'c and
Pat Morin and
Ryuhei Uehara Ghost Chimneys . . . . . . . . . . . . . 207
Danny Z. Chen and
Haitao Wang Fitting a Step Function to a Point Set
with Outliers Based on Simplicial
Thickness Data Structures . . . . . . . 215
Giovanni Viglietta Searching Polyhedra by Rotating
Half-Planes . . . . . . . . . . . . . . 243
Ferran Hurtado and
Marc Van Kreveld Guest Editors' Foreword . . . . . . . . 277
Dominique Attali and
André Lieutier and
David Salinas Efficient Data Structure for
Representing and Simplifying Simplicial
Complexes in High Dimensions . . . . . . 279
Mridul Aanjaneya and
Frederic Chazal and
Daniel Chen and
Marc Glisse and
Leonidas Guibas and
Dmitriy Morozov Metric Graph Reconstruction from Noisy
Data . . . . . . . . . . . . . . . . . . 305
John Iacono and
Wolfgang Mulzer A Static Optimality Transformation with
Applications to Planar Point Location 327
Timothy M. Chan Three Problems About Dynamic Convex
Hulls . . . . . . . . . . . . . . . . . 341
Rishi Gupta and
Piotr Indyk and
Eric Price and
Yaron Rachlin Compressive Sensing with Local Geometric
Features . . . . . . . . . . . . . . . . 365
Danny Z. Chen and
Haitao Wang Locating an Obnoxious Line Among Planar
Objects . . . . . . . . . . . . . . . . 391
Gautam K. Das and
Robert Fraser and
Alejandro Lóopez-Ortiz and
Bradford G. Nickerson On the Discrete Unit Disk Cover Problem 407
Carmen Cortés and
Delia Garijo and
María Ángeles Garrido and
Clara I. Grima and
Alberto Márquez and
Auxiliadora Moreno-González and
Jesús Valenzuela and
María Trinidad Villar Reporting Bichromatic Segment
Intersections from Point Sets . . . . . 421
Prosenjit Bose and
Vida Dujmovi\'c and
Ferran Hurtado and
John Iacono and
Stefan Langerman and
Henk Meijer and
Vera Sacristán and
Maria Saumell and
David R. Wood Proximity Graphs: $E$, $ \delta $, $
\Delta $, $ \chi $ and $ \omega $ . . . 439
Stefan Huber and
Martin Held A Fast Straight-Skeleton Algorithm Based
on Generalized Motorcycle Graphs . . . . 471
Thomas Binder and
Thomas Martinetz On the Boundedness of an Iteration
Involving Points on the Hypersphere . . 499
Yonatan Myers and
Leo Joskowicz Point Set Distance and Orthogonal Range
Problems with Dependent Geometric
Uncertainties . . . . . . . . . . . . . 517
Hooman Reisi Dehkordi and
Peter Eades Every Outer-$1$-Plane Graph Has a Right
Angle Crossing Drawing . . . . . . . . . 543
Manuel Abellanas and
Merc\`e Claverol and
Gregorio Hernández and
Ferran Hurtado and
Vera Sacristán and
Maria Saumell and
Rodrigo I. Silveira Improving Shortest Paths in the Delaunay
Triangulation . . . . . . . . . . . . . 559
Viet-Hang Nguyen $1$-Extensions and Global Rigidity of
Generic Direction-Length Frameworks . . 577
Anonymous Author Index Volume 22 (2012) . . . . . 593
Victor Milenkovic and
Elisha Sacks and
Steven Trac Planar Shape Manipulation Using
Approximate Geometric Primitives . . . . 1
Mark De Berg and
Dirk H. P. Gerrits Computing Push Plans for Disk-Shaped
Robots . . . . . . . . . . . . . . . . . 29
Steve Butler and
Erik Demaine and
Ron Graham and
Tomohiro Tachi Constructing Points Through Folding and
Intersection . . . . . . . . . . . . . . 49
Toshihiro Shirakawa and
Ryuhei Uehara Common Developments of Three Incongruent
Orthogonal Boxes . . . . . . . . . . . . 65
Takao Asano and
Shin-Ichi Nakano and
Yoshio Okamoto Guest Editors' Foreword . . . . . . . . 73
Zachary Abel and
Erik D. Demaine and
Martin L. Demaine and
Sarah Eisenstat and
Jayson Lynch and
Tao B. Schardl and
Isaac Shapiro-Ellowitz Folding Equilateral Plane Graphs . . . . 75
Patrizio Angelini and
Giuseppe Di Battista and
Fabrizio Frati Simultaneous Embedding of Embedded
Planar Graphs . . . . . . . . . . . . . 93
Adrian Dumitrescu and
Masud Hasan Cutting Out Polygons with a Circular Saw 127
Yakov Nekrich External Memory Orthogonal Range
Reporting with Fast Updates . . . . . . 141
Otfried Cheong and
Changryeol Lee Single-Source Dilation-Bounded Minimum
Spanning Trees . . . . . . . . . . . . . 159
P. A. Grossman and
M. Brazil and
J. H. Rubinstein and
D. A. Thomas Minimal Curvature-Constrained Paths in
the Plane with a Constraint on Arcs with
Opposite Orientations . . . . . . . . . 171
Tirasan Khandhawit and
Dimitrios Pagonakis and
Sira Sriswasdi Lower Bound for Convex Hull Area and
Universal Cover Problems . . . . . . . . 197
Ferran Hurtado and
Giuseppe Liotta and
David R. Wood Proximity Drawings of High-Degree Trees 213
Gill Barequet Editor's Foreword . . . . . . . . . . . 231
Peyman Afshani Improved Pointer Machine and I/O Lower
Bounds for Simplex Range Reporting and
Related Problems . . . . . . . . . . . . 233
Amirali Abdullah and
John Moeller and
Suresh Venkatasubramanian Approximate Bregman Near Neighbors in
Sublinear Time: Beyond the Triangle
Inequality . . . . . . . . . . . . . . . 253
Jean-Daniel Boissonnat and
Ramsay Dyer and
Arijit Ghosh The Stability of Delaunay Triangulations 303
Haim Kaplan and
Micha Sharir Finding the Largest Empty Disk
Containing a Query Point . . . . . . . . 335
Therese Biedl and
Martin Vatshelle The Point-Set Embeddability Problem for
Plane Graphs . . . . . . . . . . . . . . 357
Ioannis Z. Emiris and
Vissarion Fisikopoulos and
Christos Konaxis and
Luis Peñaranda An Oracle-Based, Output-Sensitive
Algorithm for Projections of Resultant
Polytopes . . . . . . . . . . . . . . . 397
Kun-Mao Chao and
Tsan-Sheng Hsu and
Der-Tsai Lee Guest Editors' Foreword . . . . . . . . 425
Stephane Durocher and
Alexandre Leblanc and
Jason Morrison and
Matthew Skala Robust Nonparametric Simplification of
Polygonal Chains . . . . . . . . . . . . 427
Evanthia Papadopoulou and
Sandeep Kumar Dey On the Farthest Line-Segment Voronoi
Diagram . . . . . . . . . . . . . . . . 443
Minati De and
Gautam K. Das and
Paz Carmi and
Subhas C. Nandy Approximation Algorithms for a Variant
of Discrete Piercing Set Problem for
Unit Disks . . . . . . . . . . . . . . . 461
Anonymous Author Index Volume 23 (2013) . . . . . 479
Daniela Maftuleac Algorithms for Distance Problems in
Planar Complexes of Global Nonpositive
Curvature . . . . . . . . . . . . . . . 1
Alexander Reshetov A Unistable Polyhedron with $ 14 $ Faces 39
Stefan Huber and
Martin Held and
Peter Meerwald and
Roland Kwitt Topology-Preserving Watermarking of
Vector Graphics . . . . . . . . . . . . 61
Marcus Brazil and
Martin Zachariasen The Uniform Orientation Steiner Tree
Problem Is NP-Hard . . . . . . . . . . . 87
Hee-Kap Ahn and
Hyo-Sil Kim and
Sang-Sub Kim and
Wanbin Son Computing $k$ Centers over Streaming
Data for Small $k$ . . . . . . . . . . . 107
Jean-Daniel Boissonnat and
Ramsay Dyer and
Arijit Ghosh Delaunay Stability Via Perturbations . . 125
Abhijeet Khopkar and
Sathish Govindarajan Hardness Results for Computing Optimal
Locally Gabriel Graphs . . . . . . . . . 153
J. M. Díaz-Báñez and
R. Klein and
J. Urrutia Editors' Foreword . . . . . . . . . . . 173
Ruy Fabila-Monroy and
Clemens Huemer and
Eul\`alia Tramuns Note on the Number of Obtuse Angles in
Point Sets . . . . . . . . . . . . . . . 177
S. Bereg and
J. M. Díaz-Báñez and
M. Fort and
M. A. Lopez and
P. Pérez-Lantero and
J. Urrutia Continuous Surveillance of Points by
Rotating Floodlights . . . . . . . . . . 183
Oswin Aichholzer and
Thomas Hackl and
David Orden and
Alexander Pilz and
Maria Saumell and
Birgit Vogtenhuber Flips in Combinatorial Pointed
Pseudo-Triangulations with Face Degree
at Most Four . . . . . . . . . . . . . . 197
David Kirkpatrick and
Boting Yang and
Sandra Zilles A Polynomial-Time Algorithm for
Computing the Resilience of Arrangements
of Ray Sensors . . . . . . . . . . . . . 225
Javier Cano and
Ferran Hurtado and
Jorge Urrutia Stabbing Simplices of Point Sets with
$k$-Flats . . . . . . . . . . . . . . . 237
S. Bereg and
R. Fabila-Monroy and
D. Flores-Peñaloza and
M. A. Lopez and
P. Pérez-Lantero Embedding the Double Circle in a Square
Grid of Minimum Size . . . . . . . . . . 247
Hee-Kap Ahn and
Antoine Vigneron Guest Editors' Foreword . . . . . . . . 259
Wolfgang Mulzer and
Yannik Stein Algorithms for Tolerant Tverberg
Partitions . . . . . . . . . . . . . . . 261
Ferran Hurtado and
Maarten Löffler and
Inês Matos and
Vera Sacristán and
Maria Saumell and
Rodrigo I. Silveira and
Frank Staals Terrain Visibility with Multiple
Viewpoints . . . . . . . . . . . . . . . 275
Oswin Aichholzer and
Thomas Hackl and
Matias Korman and
Alexander Pilz and
Birgit Vogtenhuber Geodesic-Preserving Polygon
Simplification . . . . . . . . . . . . . 307
Patrizio Angelini and
Thomas Bläsius and
Ignaz Rutter Testing Mutual Duality of Planar Graphs 325
Cecilia Bohler and
Rolf Klein Abstract Voronoi Diagrams with
Disconnected Regions . . . . . . . . . . 347
Kevin Buchin and
Dirk H. P. Gerrits Dynamic Point Labeling Is Strongly
Pspace-Complete . . . . . . . . . . . . 373
Anonymous Author Index: Volume 24 (2014) . . . . . 397
Minghui Jiang On Covering Points with Minimum Turns 1
Vladimir Estivill-Castro Is It FPT to Cover Points with Tours on
Minimum Number of Bends (Errata)? . . . 11
Bettina Speckmann and
Kevin Verbeek Algorithms for Necklace Maps . . . . . . 15
David J. T. Liu and
Qiang Du Optimization of Subdivision Invariant
Tetrahedra . . . . . . . . . . . . . . . 37
Haitao Wang Aggregate-MAX Top-$k$ Nearest Neighbor
Searching in the $ L_1$ Plane . . . . . 57
Brendan Ames and
Andrew Beveridge and
Rosalie Carlson and
Claire Djang and
Volkan Isler and
Stephen Ragain and
Maxray Savage A Leapfrog Strategy for Pursuit-Evasion
in a Polygonal Environment . . . . . . . ??
David Eppstein and
Marc van Kreveld and
Bettina Speckmann and
Frank Staals Improved Grid Map Layout by Point Set
Matching . . . . . . . . . . . . . . . . ??
Evanthia Papadopoulou and
Jinhui Xu The $ L_\infty $ Hausdorff Voronoi
Diagram Revisited . . . . . . . . . . . ??
Julien André and
Dominique Attali and
Quentin Mérigot and
Boris Thibert Far-Field Reflector Problem Under Design
Constraints . . . . . . . . . . . . . . ??
Nabil H. Mustafa and
Saurabh Ray and
Nabil H. Mustafa $k$-Centerpoints Conjectures for
Pointsets in $ \mathbb {R}^d$ . . . . . ??
Niccol\`o Cavazza and
Massimo Ferri and
Claudia Landi Estimating Multidimensional Persistent
Homology Through a Finite Sampling . . . ??
Simon Willerton Spread: A Measure of the Size of Metric
Spaces . . . . . . . . . . . . . . . . . ??
Paz Carmi and
Gautam K. Das and
Ramesh K. Jallu and
Subhas C. Nandy and
Prajwal R. Prasad and
Yael Stein Minimum Dominating Set Problem for Unit
Disks Revisited . . . . . . . . . . . . ??
John Gunnar Carlsson and
Benjamin Armbruster and
Saladi Rahul and
Haritha Bellam A Bottleneck Matching Problem with
Edge-Crossing Constraints . . . . . . . 245
Priya Ranjan Sinha Mahapatra and
Partha P. Goswami and
Sandip Das Placing Two Axis-Parallel Squares to
Maximize the Number of Enclosed Points 263
Oswin Aichholzer and
Franz Aurenhammer and
Thomas Hackl and
Clemens Huemer and
Alexander Pilz and
Birgit Vogtenhuber $3$-Colorability of
Pseudo-Triangulations . . . . . . . . . 283
Frank Duque and
Carlos Hidalgo-Toscano An Upper Bound on the $k$-Modem
Illumination Problem . . . . . . . . . . 299
Anonymous Author Index Volume 25 (2015) . . . . . 309
Bodhayan Roy Point Visibility Graph Recognition is
NP-Hard . . . . . . . . . . . . . . . . 1
Christian Scheffer More Flexible Curve Matching via the
Partial Fréchet Similarity . . . . . . . 33
M. I. Schlesinger and
E. V. Vodolazskiy and
V. M. Yakovenko Fréchet Similarity of Closed Polygonal
Curves . . . . . . . . . . . . . . . . . 53
Pradeesha Ashok and
Sathish Govindarajan and
Ninad Rajgopal Selection Lemmas for Various Geometric
Objects . . . . . . . . . . . . . . . . 67
Adrian Dumitrescu and
Anirban Ghosh Lower Bounds on the Dilation of Plane
Spanners . . . . . . . . . . . . . . . . 89
Lucas Moutinho Bueno and
Jorge Stolfi $3$-Colored Triangulation of $2$D Maps 111--133
Christian Knauer and
Michiel Smid Guest Editors' Foreword . . . . . . . . iii--iv
Prosenjit Bose and
Pat Morin and
André van Renssen The Price of Order . . . . . . . . . . . 135--149
Subhash Suri and
Kevin Verbeek On the Most Likely Voronoi Diagram and
Nearest Neighbor Searching . . . . . . . 151--166
Oswin Aichholzer and
Jean Cardinal and
Vincent Kusters and
Stefan Langerman and
Pavel Valtr Reconstructing Point Set Order Types
from Radial Orderings . . . . . . . . . 167--184
Haitao Wang and
Jingru Zhang Line-Constrained $k$-Median, $k$-Means,
and $k$-Center Problems in the Plane . . 185--210
Therese Biedl and
Stefan Huber and
Peter Palfrader Planar Matchings for Weighted Straight
Skeletons . . . . . . . . . . . . . . . 211--229
Anonymous Author Index Volume 26 (2016) . . . . . 231--231
Mark de Berg and
Adrian Dumitrescu and
Khaled Elbassioni Guest Editors' Foreword . . . . . . . . 1--2
Siu-Wing Cheng and
Man-Kit Lau Adaptive Point Location in Planar Convex
Subdivisions . . . . . . . . . . . . . . 3--12
Siu-Wing Cheng and
Man-Kwun Chiu and
Jiongxin Jin and
Antoine Vigneron Navigating Weighted Regions with
Scattered Skinny Tetrahedra . . . . . . 13--32
Yi-Jun Chang and
Hsu-Chun Yen Improved Algorithms for Grid-Unfolding
Orthogonal Polyhedra . . . . . . . . . . 33--56
Oswin Aichholzer and
Vincent Kusters and
Wolfgang Mulzer and
Alexander Pilz and
Manuel Wettstein An Optimal Algorithm for Reconstructing
Point Set Order Types from Radial
Orderings . . . . . . . . . . . . . . . 57--83
Karl Bringmann and
Marvin Künnemann Improved Approximation for Fréchet
Distance on $c$-Packed Curves Matching
Conditional Lower Bounds . . . . . . . . 85--119
Martin Nöllenburg and
Roman Prutkin and
Ignaz Rutter Partitioning Graph Drawings and
Triangulated Simple Polygons into
Greedily Routable Regions . . . . . . . 121--158
Helmut Alt and
Sergio Cabello and
Panos Giannopoulos and
Christian Knauer Minimum Cell Connection in Line Segment
Arrangements . . . . . . . . . . . . . . 159--176
Juyoung Yon and
Siu-Wing Cheng and
Otfried Cheong and
Antoine Vigneron Finding Largest Common Point Sets . . . 177--185
Victor C. S. Lee and
Haitao Wang and
Xiao Zhang Minimizing the Maximum Moving Cost of
Interval Coverage . . . . . . . . . . . 187--205
A. Karim Abu-Affash and
Paz Carmi and
Anat Parush Tzur Strongly Connected Spanning Subgraph for
Almost Symmetric Networks . . . . . . . 207--219
Cecilia Bohler and
Rolf Klein and
Chih-Hung Liu Abstract Voronoi Diagrams from Closed
Bisecting Curves . . . . . . . . . . . . 221--240
Prosenjit Bose and
Jean-Lou De Carufel and
Stephane Durocher and
Perouz Taslakian Competitive Online Routing on Delaunay
Triangulations . . . . . . . . . . . . . 241
Guilherme D. da Fonseca and
Vinícius Gusmão Pereira de Sá and
Celina Miraglia Herrera de Figueiredo Shifting Coresets: Obtaining Linear-Time
Approximations for Unit Disk Graphs and
Other Geometric Intersection Graphs . . 255
Vincent Froese and
Iyad Kanj and
André Nichterlein and
Rolf Niedermeier Finding Points in General Position . . . 277
Lucas Moutinho Bueno and
Jorge Stolfi $4$-Colored Triangulation of $3$-Maps 297
Anonymous Author Index Volume 27 (2017) . . . . . 327
Michelle Hatch Hummel and
Bihua Yu and
Carlos Simmerling and
Evangelos A. Coutsias Laguerre-Intersection Method for
Implicit Solvation . . . . . . . . . . . 1
Jude Buot and
Mikio Kano Weight-Equitable Subdivision of Red and
Blue Points in the Plane . . . . . . . . 39
Kenes Beketayev and
Damir Yeliussizov and
Dmitriy Morozov and
Gunther H. Weber and
Bernd Hamann Measuring the Error in Approximating the
Sub-Level Set Topology of Sampled Scalar
Data . . . . . . . . . . . . . . . . . . 57
Seok-Hee Hong Guest Editor's Foreword . . . . . . . . ??
Hung-I Yu and
Tien-Ching Lin and
D. T. Lee The $ (1 | 1)$-Centroid Problem in the
Plane with Distance Constraints . . . . ??
Helmut Alt and
Nadja Scharf Approximating Smallest Containers for
Packing Three-Dimensional Convex Objects ??
Sándor P. Fekete and
Qian Li and
Joseph S. B. Mitchell and
Christian Scheffer Universal Guard Problems . . . . . . . . ??
Hugo A. Akitaya and
Csaba D. Tóth Reconstruction of Weakly Simple Polygons
from Their Edges . . . . . . . . . . . . ??
Marc van Kreveld and
Maarten Löffler and
Frank Staals and
Lionov Wiratma A Refined Definition for Groups of
Moving Entities and Its Computation . . ??
Oswin Aichholzer and
Michael Biro and
Erik D. Demaine and
Martin L. Demaine and
David Eppstein and
Sándor P. Fekete and
Adam Hesterberg and
Irina Kostitsyna and
Christiane Schmidt Folding Polyominoes into (Poly)Cubes . . ??
Fabrizio d'Amore and
Paolo G. Franciosa A Low Arithmetic-Degree Algorithm for
Computing Proximity Graphs . . . . . . . ??
Olivier Devillers and
Louis Noizet Walking in a Planar Poisson--Delaunay
Triangulation: Shortcuts in the Voronoi
Path . . . . . . . . . . . . . . . . . . ??
Haitao Wang and
Jingru Zhang Computing the Rectilinear Center of
Uncertain Points in the Plane . . . . . ??
Sándor P. Fekete and
Phillip Keldenich Conflict-Free Coloring of Intersection
Graphs . . . . . . . . . . . . . . . . . ??
Günther Eder and
Martin Held and
Peter Palfrader Min-/Max-Volume Roofs Induced by
Bisector Graphs of Polygonal Footprints
of Buildings . . . . . . . . . . . . . . 309--340
Rom Aschner and
Paz Carmi and
Yael Stein Unique Coverage with Rectangular Regions 341--363
Sourav Chakraborty and
Rameshwar Pratap and
Sasanka Roy and
Shubhangi Saraf Helly-Type Theorems in Property Testing 365--379
Stephane Durocher and
Robert Fraser and
Alexandre Leblanc and
Jason Morrison and
Matthew Skala On Combinatorial Depth Measures . . . . 381--398
Anonymous Author Index Volume 28 (2018) . . . . . 399--400
Takeshi Tokuyama Guest Editor's Foreword . . . . . . . . 1--1
Kazuyuki Amano and
Yoshinobu Haruyama On the Number of p4-Tilings by an
$n$-Omino . . . . . . . . . . . . . . . 3--19
Mark de Berg and
Ade Gunawan and
Marcel Roeloffzen Faster DBSCAN and HDBSCAN in
Low-Dimensional Euclidean Spaces . . . . 21--47
Mark de Berg and
Tim Leijsen and
Aleksandar Markovic and
André van Renssen and
Marcel Roeloffzen and
Gerhard Woeginger Fully-Dynamic and Kinetic Conflict-Free
Coloring of Intervals with Respect to
Points . . . . . . . . . . . . . . . . . 49--72
Gregory Bint and
Anil Maheshwari and
Michiel Smid and
Subhas C. Nandy Partial Enclosure Range Searching . . . 73--93
Prosenjit Bose and
André van Renssen Spanning Properties of Yao and $ \theta
$-Graphs in the Presence of Constraints 95--120
Patrick J. Andersen and
Charl J. Ras Algorithms for Euclidean Degree Bounded
Spanning Tree Problems . . . . . . . . . 121--160
Joachim Gudmundsson and
Majid Mirzanezhad and
Ali Mohades and
Carola Wenk Fast Fréchet Distance Between Curves with
Long Edges . . . . . . . . . . . . . . . 161--187
Haitao Wang and
Wuzhou Zhang On Top-$k$ Weighted Sum Aggregate
Nearest and Farthest Neighbors in the $
L_1 $ Plane . . . . . . . . . . . . . . 189--218
Victor Milenkovic and
Elisha Sacks and
Nabeel Butt Fast Detection of Degenerate Predicates
in Free Space Construction . . . . . . . 219--237
Günther Eder and
Martin Held Weighted Voronoi Diagrams in the Maximum
Norm . . . . . . . . . . . . . . . . . . 239--250
Günther Eder and
Martin Held and
Peter Palfrader Recognizing Geometric Trees as
Positively Weighted Straight Skeletons
and Reconstructing Their Input . . . . . 251--267
Paz Carmi and
Farah Chanchary and
Anil Maheshwari and
Michiel Smid The Most Likely Object to be Seen
Through a Window . . . . . . . . . . . . 269--287
Alexander Pilz and
Carlos Seara Convex Quadrangulations of Bichromatic
Point Sets . . . . . . . . . . . . . . . 289--299
Danny Rorabaugh A Bound on a Convexity Measure for Point
Sets . . . . . . . . . . . . . . . . . . 301--306
Lindsay Berry and
Andrew Beveridge and
Jane Butterfield and
Volkan Isler and
Zachary Keller and
Alana Shine and
Junyi Wang Line-of-Sight Pursuit in Monotone and
Scallop Polygons . . . . . . . . . . . . 307--351
Anonymous Author Index Volume 29 (2019) . . . . . 353--354
Prosenjit Bose and
Stephane Durocher and
Debajyoti Mondal and
Maxime Peabody and
Matthew Skala and
Mohammad Abdul Wahid Local Routing in Convex Subdivisions . . 1--17
Daniel Kraft Computing the Hausdorff Distance of Two
Sets from Their Distance Functions . . . 19--49
R. Inkulu and
K. Sowmya and
Nitish P. Thakur Dynamic Algorithms for Visibility
Polygons in Simple Polygons . . . . . . 51--78
Binayak Dutta and
Sasanka Roy Approximate Shortest Paths in Polygons
with Violations . . . . . . . . . . . . 79--95
Bengt J. Nilsson and
Pawe\l \. Zyli\'nski How to Keep an Eye on Small Things . . . 97--120
Bogdan Grechuk and
Sittichoke Som-am A Convex Cover for Closed Unit Curves
has Area at Least 0.0975 . . . . . . . . 121--139
Michael Kerber and
Arnur Nigmetov Metric Spaces with Expensive Distances 141--165
Haitao Wang and
Yiming Zhao A Linear-Time Algorithm for Discrete
Radius Optimally Augmenting Paths in a
Metric Space . . . . . . . . . . . . . . 167--182
Prashant Gupta and
Bala Krishnamoorthy Euler Transformation of Polyhedral
Complexes . . . . . . . . . . . . . . . 183--211
Yangwei Liu and
Hu Ding and
Ziyun Huang and
Jinhui Xu Distributed and Robust Support Vector
Machine . . . . . . . . . . . . . . . . 213--233
Bastian Weiß and
Bert Jüttler and
Franz Aurenhammer Mitered Offsets and Skeletons for
Circular Arc Polygons . . . . . . . . . 235--256
Anonymous Author Index Volume 30 (2020) . . . . . ??
Matthew Johnson and
Daniël Paulusma and
Erik Jan Van Leeuwen What Graphs are 2-Dot Product Graphs? 1--16
Hédi Nabli Truchet Tiles and Combinatorial
Arabesque . . . . . . . . . . . . . . . 17--37
Alexander Stoimenow Exchangeability and Non-Conjugacy of
Braid Representatives . . . . . . . . . 39--73
Rivka Gitik and
Leo Joskowicz Voronoi Diagram and Delaunay
Triangulation with Independent and
Dependent Geometric Uncertainties . . . 75--121
Debangshu Banerjee and
R. Inkulu Vertex Guarding for Dynamic Orthogonal
Art Galleries . . . . . . . . . . . . . 123--140
Václav Bla\vzj and
Ji\vrí Fiala and
Giuseppe Liotta On Edge-Length Ratios of Partial 2-Trees 141--162
Haohao Wang and
Ron Goldman Ruled Surfaces of Revolution with Moving
Axes and Angles . . . . . . . . . . . . 163--181
Sergey Korotov and
Lars Fredrik Lund and
Jon Eivind Vatne Improved Maximum Angle Estimate for
Longest-Edge Bisection . . . . . . . . . 183--192
Prashant Gupta and
Yiran Guo and
Narasimha Boddeti and
Bala Krishnamoorthy SFCDecomp: Multicriteria Optimized Tool
Path Planning in $3$D Printing using
Space-Filling Curve Based Domain
Decomposition . . . . . . . . . . . . . 193--220
Kazuma Tateiri and
Toru Ohmoto An Extended MMP Algorithm: Wavefront and
Cut-Locus on a Convex Polyhedron . . . . 221--247
Anonymous Author Index Volume 31 (2021) . . . . . ??
Henry Adams and
Sophia Coldren and
Sean Willmot The Persistent Homology of Cyclic Graphs 1--37
Victor Milenkovic and
Elisha Sacks Efficient Predicate Evaluation Using
Randomized Degeneracy Detection . . . . 39--54
Christopher G. Provatidis Non-Rational and Rational Transfinite
Interpolation Using Bernstein
Polynomials . . . . . . . . . . . . . . 55--89
Brittany Terese Fasy and
Rafal Komendarczyk and
Sushovan Majhi and
Carola Wenk On the Reconstruction of Geodesic
Subspaces of $ \mathbb {R}^N $ . . . . . 91--117
Vincent Guigues Algorithms and a Library for the Exact
Computation of the Cumulative
Distribution Function of the Euclidean
Distance Between a Point and a Random
Variable Uniformly Distributed in Disks,
Balls, or Polygones and Application to
Probabilistic Seismic Hazard Analysis 119--174
Sukanya Bhattacharjee and
R. Inkulu Vertex Fault-Tolerant Geometric Spanners
for Weighted Points . . . . . . . . . . 175--199
Jiawei Huang and
Ruizhe Qin and
Fan Yang and
Hu Ding Random Projection and Recovery for High
Dimensional Optimization with Arbitrary
Outliers . . . . . . . . . . . . . . . . 201--225
Anonymous Author Index Volume 32 (2022) . . . . . ??
Wing-kai Hon and
Chung-shou Liao and
Meng-tsung Tsai Guest Editors' Foreword . . . . . . . . 1--2
Travis Gagie and
Mozhgan Saeidi and
Allan Sapucaia Ruler Wrapping . . . . . . . . . . . . . 3--12
Shin-ichi Nakano The Coverage Problem by Aligned Disks 13--23
Stephane Durocher and
J. Mark Keil and
Saeed Mehrabi and
Debajyoti Mondal Bottleneck Convex Subsets: Finding $k$
Large Convex Sets in a Point Set . . . . 25--41
Kuo-kai Lee and
Wing-kai Hon and
Chung-shou Liao and
Kunihiko Sadakane and
Meng-tsung Tsai Fully Dynamic No-Back-Edge-Traversal
Forest via $2$D-Range Queries . . . . . 43--54
Chao Yang Tiling the Plane with a Set of Ten
Polyominoes . . . . . . . . . . . . . . 55--64
Abderrazzak Benroummane Some Results on Semi-Symmetric Spaces 65--84
Sergey Korotov and
Jon Eivind Vatne On Dihedral Angle Sums of Prisms and
Hexahedra . . . . . . . . . . . . . . . 85--95
Kazuma Tateiri Efficient Exact Enumeration of
Single-Source Geodesics on a Non-Convex
Polyhedron . . . . . . . . . . . . . . . 97--132
Satyabrata Jana and
Anil Maheshwari and
Saeed Mehrabi and
And Sasanka Roy Maximum Bipartite Subgraphs of Geometric
Intersection Graphs . . . . . . . . . . 133--157
Anonymous Author Index Volume 33 (2023) . . . . . ??
Princy Jain and
Haitao Wang Algorithms for Covering Barrier Points
by Mobile Sensors with Line Constraint 1--23
Awatif Al-jedani On the Curvature Functions of Ruled
Surface . . . . . . . . . . . . . . . . 25--41
Ziyun Huang and
Yongding Zhu and
And Jinhui Xu An Efficient Algorithm for the 2-Central
Path Problem . . . . . . . . . . . . . . 43--61
Yangwei Liu and
Ziyun Huang and
And Jinhui Xu A Space-Efficient One-Pass Online SVM
Algorithm . . . . . . . . . . . . . . . 63--79