Showing 2021Show all
3 papers · 1 filter
cs.CG2021
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…
cs.CG2021
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…
cs.CG2021
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…