Guest Editors’ Foreword
E. D. Giacomo, A. Lubiw
2017
Citations
0
Citations
Journal
Discrete & Computational Geometry
Full text
Semantic Scholar
Key Takeaway Key Takeaway: This special issue features nine papers from the 32nd Annual ACM Symposium on Computational Geometry, including an O(n log n) time algorithm for determining weakly simple polygons, and an O(n n) time algorithm for updating a Voronoi diagram.
Abstract
This special issue of Discrete & Computational Geometry contains a selection of the best papers thatwere presented at the 32ndAnnual ACM Symposium on Computational Geometry, which was held in Boston, USA, on June 14–17, 2016. The nine papers in this special issue were invited, submitted, reviewed, and revised according to the usual high standards of this journal. It is our pleasure to briefly introduce these contributions. Eyal Ackerman, Balázs Keszegh and Mate Vizer consider the question of whether for a given finite set S of points in the plane and a geometric object Q, there is a constant m such that the points of S can be colored red and blue so that any homothet of Q that contains at least m points of S will contain a red point and a blue point. The main result is that such a constant exists when Q is a parallelogram. Hugo Akitaya, Greg Aloupis, Jeff Erickson and Csaba Tóth present an O(n log n) time algorithm to determine whether a polygon with n vertices is weakly simple. This improves the previous running time of O(n2 log n) time presented by Hsien-Chih Chang, Jeff Erickson and Chao Xu at SODA’15. Sarah Allen, Luis Barba, John Iacono and Stefan Langerman discuss the amortized number of combinatorial changes needed to update aVoronoi diagramof a set of n sites in the plane, as the sites are added to the set. For a newly defined update operation, they show that the amortized cost is O( √ n) (where cost is the minimum number of edge insertions and removals needed). They also present an output-sensitive data structure