John Iacono

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Competitive Online Search Trees on Trees.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, July, 2023

Scalable Data Structures (Dagstuhl Seminar 23211).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2023

Subquadratic algorithms for some 3Sum-hard geometric problems in the algebraic decision-tree model.

[BibT_eX]

[DOI]

Comput. Geom., 2023

2022

Fragile complexity of adaptive algorithms.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

External-Memory Dictionaries with Worst-Case Update Cost.

[BibT_eX]

[DOI]

Rathish Das

Yakov Nekrich

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

How Fast Can We Play Tetris Greedily with Rectangular Pieces?

[BibT_eX]

[DOI]

Proceedings of the 11th International Conference on Fun with Algorithms, 2022

Conditional Lower Bounds for Dynamic Geometric Measure Problems.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

Locality-of-Reference Optimality of Cache-Oblivious Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 3rd Symposium on Algorithmic Principles of Computer Systems, 2022

2021

Belga B-Trees.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2021

Scalable Data Structures (Dagstuhl Seminar 21071).

[BibT_eX]

[DOI]

Markus E. Nebel

Vijaya Ramachandran

Dagstuhl Reports, 2021

Dynamic Schnyder Woods.

[BibT_eX]

[DOI]

CoRR, 2021

Modular Subset Sum, Dynamic Strings, and Zero-Sum Sets.

[BibT_eX]

[DOI]

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Worst-Case Efficient Dynamic Geometric Independent Set.

[BibT_eX]

[DOI]

Grigorios Koumoutsos

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

Approximability of (Simultaneous) Class Cover for Boxes.

[BibT_eX]

Proceedings of the 33rd Canadian Conference on Computational Geometry, 2021

2020

Sublinear Explicit Incremental Planar Voronoi Diagrams.

[BibT_eX]

[DOI]

J. Inf. Process., 2020

Spanning Properties of Theta-Theta-6.

[BibT_eX]

[DOI]

Mirela Damian

Andrew Winslow

Graphs Comb., 2020

Dynamic Geometric Independent Set.

[BibT_eX]

[DOI]

CoRR, 2020

2019

Subquadratic encodings for point configurations.

[BibT_eX]

[DOI]

J. Comput. Geom., 2019

Subquadratic Algorithms for Algebraic 3SUM.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2019

A parallel priority queue with fast updates for GPU architectures.

[BibT_eX]

[DOI]

Ben Karsin

Nodari Sitchinava

CoRR, 2019

Encoding 3SUM.

[BibT_eX]

[DOI]

CoRR, 2019

Locality.

[BibT_eX]

[DOI]

Varunkumar Jayapaul

Ben Karsin

CoRR, 2019

External Memory Planar Point Location with Fast Updates.

[BibT_eX]

[DOI]

Ben Karsin

Grigorios Koumoutsos

Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms.

[BibT_eX]

[DOI]

Riko Jacob

Konstantinos Tsakalidis

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Encoding nearest larger values.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams.

[BibT_eX]

[DOI]

Algorithmica, 2018

Analysis-driven Engineering of Comparison-based Sorting Algorithms on GPUs.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Conference on Supercomputing, 2018

Dynamic Trees with Almost-Optimal Access Cost.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Compatible Paths on Labelled Point Sets.

[BibT_eX]

[DOI]

Proceedings of the 30th Canadian Conference on Computational Geometry, 2018

2017

Asymptotically Optimal Encodings of Range Data Structures for Selection and Top-k Queries.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2017

Incremental Voronoi Diagrams.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2017

An Efficient Multiway Mergesort for GPU Architectures.

[BibT_eX]

[DOI]

CoRR, 2017

Searching Edges in the Overlap of Two Plane Graphs.

[BibT_eX]

[DOI]

Elena Khramtcova

Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

Subquadratic Algorithms for Algebraic Generalizations of 3SUM.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

Nearest-Neighbor Search Under Uncertainty.

[BibT_eX]

Boris Aronov

Khadijeh Sheikhan

Proceedings of the 29th Canadian Conference on Computational Geometry, 2017

2016

Encoding 2D range maximum queries.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

The Power and Limitations of Static Binary Search Trees with Lazy Finger.

[BibT_eX]

[DOI]

Algorithmica, 2016

Weighted dynamic finger in binary search trees.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Solving k-SUM Using Few Linear Queries.

[BibT_eX]

[DOI]

Aurélien Ooms

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

A Linear Potential Function for Pairing Heaps.

[BibT_eX]

[DOI]

Mark V. Yagnatinsky

Proceedings of the Combinatorial Optimization and Applications, 2016

2015

Worst-Case Optimal Tree Layout in External Memory.

[BibT_eX]

[DOI]

Algorithmica, 2015

Range Minimum Query Indexes in Higher Dimensions.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

2014

A Tight Lower Bound for Decrease-Key in the Pure Heap Model.

[BibT_eX]

[DOI]

Özgür Özkan

CoRR, 2014

Foreword.

[BibT_eX]

[DOI]

Frank Dehne

Comput. Geom., 2014

Necklaces, Convolutions, and X+Y.

[BibT_eX]

[DOI]

Algorithmica, 2014

The Complexity of Order Type Isomorphism.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Why Some Heaps Support Constant-Amortized-Time Decrease-Key Operations, and Others Do Not.

[BibT_eX]

[DOI]

Özgür Özkan

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Cache-Oblivious Persistence.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2014, 2014

2013

Coverage with k-transmitters in the presence of obstacles.

[BibT_eX]

[DOI]

Vera Sacristán Adinolfi

Diane L. Souvaine

Ryuhei Uehara

J. Comb. Optim., 2013

The Fresh-Finger Property

[BibT_eX]

[DOI]

John Howat

Pat Morin

CoRR, 2013

Why some heaps support constant-amortized-time decrease-key operations, and others do not

[BibT_eX]

[DOI]

CoRR, 2013

The Complexity of Order Type Isomorphism.

[BibT_eX]

[DOI]

CoRR, 2013

Oja centers and centers of gravity.

[BibT_eX]

[DOI]

Comput. Geom., 2013

Efficient reconfiguration of lattice-based modular robots.

[BibT_eX]

[DOI]

Comput. Geom., 2013

On the hierarchy of distribution-sensitive properties for data structures.

[BibT_eX]

[DOI]

Acta Informatica, 2013

Combining Binary Search Trees.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Encodings for Range Selection and Top-k Queries.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2013, 2013

How to Cover Most of a Point Set with a V-Shape of Minimum Width.

[BibT_eX]

[DOI]

Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

In Pursuit of the Dynamic Optimality Conjecture.

[BibT_eX]

[DOI]

Proceedings of the Space-Efficient Data Structures, 2013

2012

Entropy, triangulation, and point location in planar subdivisions.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

A priority queue with the time-finger property.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2012

A Static Optimality Transformation with Applications to Planar Point Location.

[BibT_eX]

[DOI]

Wolfgang Mulzer

Int. J. Comput. Geom. Appl., 2012

PROXIMITY GRAPHS: E, δ, Δ, χ AND ω.

[BibT_eX]

[DOI]

Vera Sacristán Adinolfi

Maria Saumell

David R. Wood

Int. J. Comput. Geom. Appl., 2012

Packing identical simple polygons is NP-hard

[BibT_eX]

[DOI]

Sarah R. Allen

CoRR, 2012

Using hashing to solve the dictionary problem.

[BibT_eX]

[DOI]

Mihai Patrascu

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Confluent persistence revisited.

[BibT_eX]

[DOI]

Sébastien Collette

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Continuous Blooming of Convex Polyhedra.

[BibT_eX]

[DOI]

Graphs Comb., 2011

Encoding 2-D Range Maximum Queries

[BibT_eX]

[DOI]

CoRR, 2011

Using Hashing to Solve the Dictionary Problem (In External Memory)

[BibT_eX]

[DOI]

Mihai Patrascu

CoRR, 2011

The Cost of Cache-Oblivious Searching.

[BibT_eX]

[DOI]

Michael A. Bender

Alejandro López-Ortiz

Algorithmica, 2011

Meshes Preserving Minimum Feature Size.

[BibT_eX]

[DOI]

Proceedings of the Computational Geometry - XIV Spanish Meeting on Computational Geometry, 2011

A Unifying Property for Distribution-Sensitive Priority Queues.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 22nd International Workshop, 2011

Encoding 2D Range Maximum Queries.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

A static optimality transformation with applications to planar point location.

[BibT_eX]

[DOI]

Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

2010

Grid Vertex-Unfolding Orthostacks.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2010

Priority Queues with Multiple Time Fingers

[BibT_eX]

[DOI]

CoRR, 2010

Editorial.

[BibT_eX]

[DOI]

Comput. Geom., 2010

Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Unit-Time Predecessor Queries on Massive Data Sets.

[BibT_eX]

[DOI]

Andrej Brodnik

Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

Mergeable Dictionaries.

[BibT_eX]

[DOI]

Özgür Özkan

Proceedings of the Data Structures, 28.02. - 05.03.2010, 2010

Coverage with k-Transmitters in the Presence of Obstacles.

[BibT_eX]

[DOI]

Vera Sacristán Adinolfi

Diane L. Souvaine

Ryuhei Uehara

Proceedings of the Combinatorial Optimization and Applications, 2010

Common Unfoldings of Polyominoes and Polycubes.

[BibT_eX]

[DOI]

Proceedings of the Computational Geometry, Graphs and Applications, 2010

Oja medians and centers of gravity.

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

2009

Minimum feature size preserving decompositions

[BibT_eX]

[DOI]

CoRR, 2009

Detecting all regular polygons in a point set

[BibT_eX]

[DOI]

CoRR, 2009

Wrapping spheres with flat paper.

[BibT_eX]

[DOI]

Comput. Geom., 2009

Minimal Locked Trees.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

The geometry of binary search trees.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Packing 2×2 unit squares into grid polygons is NP-complete.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual Canadian Conference on Computational Geometry, 2009

2008

Output-sensitive algorithms for Tukey depth and related problems.

[BibT_eX]

[DOI]

Stat. Comput., 2008

Distribution-sensitive point location in convex subdivisions.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Partitioning a Polygon into Two Mirror Congruent Pieces.

[BibT_eX]

Proceedings of the 20th Annual Canadian Conference on Computational Geometry, 2008

2007

A unified access bound on comparison-based dynamic dictionaries.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

Retroactive data structures.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2007

Dynamic Optimality - Almost.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Geodesic Ham-Sandwich Cuts.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2007

2006

An O(n log n)-Time Algorithm for the Restriction Scaffold Assignment Problem.

[BibT_eX]

[DOI]

J. Comput. Biol., 2006

The Complexity of Diffuse Reflections in a Simple Polygon.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Necklaces, Convolutions, and X + Y.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2006

Partitioning a Regular n-gon into n+1 Convex Congruent Pieces is Impossible, for Sufficiently Large n.

[BibT_eX]

[DOI]

Dania El-Khechen

Thomas Fevens

Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

Curves in the Sand: Algorithmic Drawing.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

2005

Separating Point Sets in Polygonal Environments.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2005

Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2005

An O(n log n)-Time Algorithm for the Restricted Scaffold Assignment

[BibT_eX]

[DOI]

CoRR, 2005

Queaps.

[BibT_eX]

[DOI]

Algorithmica, 2005

Key-Independent Optimality.

[BibT_eX]

[DOI]

Algorithmica, 2005

2004

Space-efficient planar convex hull algorithms.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

A locality-preserving cache-oblivious dynamic dictionary.

[BibT_eX]

[DOI]

J. Algorithms, 2004

Worst-Case Optimal Tree Layout in a Memory Hierarchy

[BibT_eX]

[DOI]

CoRR, 2004

Expected asymptotically optimal planar point location.

[BibT_eX]

[DOI]

Comput. Geom., 2004

Proximate point searching.

[BibT_eX]

[DOI]

Comput. Geom., 2004

2003

Proximate planar point location.

[BibT_eX]

[DOI]

Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

A 3-D visualization of kirkpatrick's planar point location algorithm.

[BibT_eX]

[DOI]

Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

2002

In-Place Planar Convex Hull Algorithms.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2002: Theoretical Informatics, 2002

2001

Alternatives to splay trees with O(log n) worst-case access times.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Optimal planar point location.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000

Improved Upper Bounds for Pairing Heaps.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2000

Volume Queries in Polyhedra.

[BibT_eX]

[DOI]

Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2000

Dynamic point location in fat hyperrectangles with integer coordinates.

[BibT_eX]

[DOI]