18 citations · 72 across the 35 of their papers we have counts for
21 papers · 1 filter
How Fast Can We Play Tetris Greedily With Rectangular Pieces?
Justin Dallant, John Iacono
Consider a variant of Tetris played on a board of width and infinite height, where the pieces are axis-aligned rectangles of arbitrary integer dimensions, the pieces can only b…
Conditional Lower Bounds for Dynamic Geometric Measure Problems
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 o…
Subquadratic Algorithms for Some \textsc{3Sum}-Hard Geometric Problems in the Algebraic Decision Tree Model
Boris Aronov, Mark de Berg, Jean Cardinal +3
We present subquadratic algorithms in the algebraic decision-tree model for several \textsc{3Sum}-hard geometric problems, all of which can be reduced to the following question: Gi…
Worst-Case Efficient Dynamic Geometric Independent Set
Jean Cardinal, John Iacono, Grigorios Koumoutsos
We consider the problem of maintaining an approximate maximum independent set of geometric objects under insertions and deletions. We present data structures that maintain a consta…
Dynamic Schnyder Woods
Sujoy Bhore, Prosenjit Bose, Pilar Cano +2
A realizer, commonly known as Schnyder woods, of a triangulation is a partition of its interior edges into three oriented rooted trees. A flip in a realizer is a local operation th…
Approximability of (Simultaneous) Class Cover for Boxes
Jean Cardinal, Justin Dallant, John Iacono
Bereg et al. (2012) introduced the Boxes Class Cover problem, which has its roots in classification and clustering applications: Given a set of n points in the plane, each colored…