JIJohn Iacono

John Iacono

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


John Iacono has a total of 715 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Conditional Lower Bounds for Dynamic Geometric Measure Problems

    by Justin Dallant, John Iacono

    We give new polynomial lower bounds for a number of dynamic measure problems in computational geometry. These lower bounds hold in the Word RAM model, conditioned on the hardness of 3SUM, APSP, or the Online Matrix-Vector Multiplication problem [Henzinger et al., STOC 2015]. In particular, we get lower bounds in the incremental and fully dynamic settings for counting maximal or extremal points in \(\mathbb{R}^{3}\) , different variants of Klee’s Measure Problem, problems related to finding the largest empty disk in a set of points, and querying the size of the i th convex layer in a planar set of points. We also answer a question of Chan et al. [SODA 2022] by giving a conditional lower bound for dynamic approximate square set cover. While many conditional lower bounds for dynamic data structures have been proven since the seminal work of Pătraşcu [STOC 2010], few of them relate to computational geometry problems. This is the first article focusing on this topic. Most problems we consider can be solved in \(O(n\log n)\) time in the static case, and their dynamic versions have only been approached from the perspective of improving known upper bounds. One exception to this is Klee’s measure problem in \(\mathbb{R}^{2}\) , for which Chan [CGTA 2010] gave an unconditional \(\Omega(\sqrt{n})\) lower bound on the worst-case update time in a variant of the Word RAM machine with large words. By a similar approach, we show that such a lower bound also holds for an important special case of Klee’s measure problem in \(\mathbb{R}^{3}\) known as the Hypervolume Indicator problem, even for amortized runtime in the incremental setting.


  • The Complexity of Order Type Isomorphism

    by Greg Aloupis, John Iacono, Stefan Langerman, Özgür Özkan, Stefanie Wuhrer

  • Open Access

    Competitive Online Search Trees on Trees

    by Prosenjit Bose, Jean Cardinal, John Iacono, Grigorios Koumoutsos, Stefan Langerman

    We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings. The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path. We describe an online O (log log n )-competitive search tree data structure in this model, where n is the number of vertices. This matches the best-known competitive ratio of binary search trees. Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one that we call Steiner-closed search trees, which may be of independent interest. Moreover, our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees and, second, from these trees into paths.


  • Fragile Complexity of Adaptive Algorithms

    by Prosenjit Bose, Pilar Cano, Rolf Fagerberg, John Iacono, Riko Jacob, Stefan Langerman


  • Encoding nearest larger values

    by Michael Hoffmann, John Iacono, Patrick K. Nicholson, Rajeev Raman


  • Open Access

    Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams

    by Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, Michiel Smid


  • Open Access

    Incremental Voronoi Diagrams

    by Sarah R. Allen, Luis Barba, John Iacono, Stefan Langerman


  • Searching Edges in the Overlap of Two Plane Graphs

    by John Iacono, Elena Khramtcova, Stefan Langerman


  • Open Access

    Searching edges in the overlap of two plane graphs

    by John Iacono, Elena Khramtcova, Stefan Langerman

    Consider a pair of plane straight-line graphs, whose edges are colored red and blue, respectively, and let n be the total complexity of both graphs. We present a O(n log n)-time O(n)-space technique to preprocess such pair of graphs, that enables efficient searches among the red-blue intersections along edges of one of the graphs. Our technique has a number of applications to geometric problems. This includes: (1) a solution to the batched red-blue search problem [Dehne et al. 2006] in O(n log n) queries to the oracle; (2) an algorithm to compute the maximum vertical distance between a pair of 3D polyhedral terrains one of which is convex in O(n log n) time, where n is the total complexity of both terrains; (3) an algorithm to construct the Hausdorff Voronoi diagram of a family of point clusters in the plane in O((n+m) log^3 n) time and O(n+m) space, where n is the total number of points in all clusters and m is the number of crossings between all clusters; (4) an algorithm to construct the farthest-color Voronoi diagram of the corners of n axis-aligned rectangles in O(n log^2 n) time; (5) an algorithm to solve the stabbing circle problem for n parallel line segments in the plane in optimal O(n log n) time. All these results are new or improve on the best known algorithms.

  • Open Access

    An Efficient Multiway Mergesort for GPU Architectures

    by Henri Casanova, John Iacono, Ben Karsin, Nodari Sitchinava, Volker Weichert

    Sorting is a primitive operation that is a building block for countless algorithms. As such, it is important to design sorting algorithms that approach peak performance on a range of hardware architectures. Graphics Processing Units (GPUs) are particularly attractive architectures as they provides massive parallelism and computing power. However, the intricacies of their compute and memory hierarchies make designing GPU-efficient algorithms challenging. In this work we present GPU Multiway Mergesort (MMS), a new GPU-efficient multiway mergesort algorithm. MMS employs a new partitioning technique that exposes the parallelism needed by modern GPU architectures. To the best of our knowledge, MMS is the first sorting algorithm for the GPU that is asymptotically optimal in terms of global memory accesses and that is completely free of shared memory bank conflicts. We realize an initial implementation of MMS, evaluate its performance on three modern GPU architectures, and compare it to competitive implementations available in state-of-the-art GPU libraries. Despite these implementations being highly optimized, MMS compares favorably, achieving performance improvements for most random inputs. Furthermore, unlike MMS, state-of-the-art algorithms are susceptible to bank conflicts. We find that for certain inputs that cause these algorithms to incur large numbers of bank conflicts, MMS can achieve up to a 37.6% speedup over its fastest competitor. Overall, even though its current implementation is not fully optimized, due to its efficient use of the memory hierarchy, MMS outperforms the fastest comparison-based sorting implementations available to date.