9 papers
Improved Bound on the Number of Pseudoline Arrangements via the Zone Theorem
Justin Dallant
Pseudoline arrangements are fundamental objects in discrete and computational geometry, and different works have tackled the problem of improving the known bounds on the number of…
An Improved Lower Bound on the Number of Pseudoline Arrangements
Fernando Cortés Kühnast, Justin Dallant, Stefan Felsner +1
Arrangements of pseudolines are classic objects in discrete and computational geometry. They have been studied with increasing intensity since their introduction almost 100 years a…
Improved Lower Bound on the Number of Pseudoline Arrangements
Justin Dallant
We show that for large enough , the number of non-isomorphic pseudoline arrangements of order is greater than for some constant , improving the…
A General Technique for Searching in Implicit Sets via Function Inversion
Boris Aronov, Jean Cardinal, Justin Dallant +1
In recent years, the Fiat-Naor function inversion scheme has been used to disprove conjectures in fine-grained complexity theory and design state of the art data structures for a n…
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…
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…
An Instance-optimal Algorithm for Bichromatic Rectangular Visibility
Jean Cardinal, Justin Dallant, John Iacono
Afshani, Barbay and Chan (2017) introduced the notion of instance-optimal algorithm in the order-oblivious setting. An algorithm A is instance-optimal in the order-oblivious settin…
Efficiently stabbing convex polygons and variants of the Hadwiger-Debrunner -theorem
Justin Dallant, Patrick Schnider
Hadwiger and Debrunner showed that for families of convex sets in with the property that among any of them some have a common point, the whole family can be…