Zobrazeno 1 - 10
of 18
pro vyhledávání: '"Dallant, Justin"'
Autor:
Dallant, Justin
We show that for large enough $n$, the number of non-isomorphic pseudoline arrangements of order $n$ is greater than $2^{c\cdot n^2}$ for some constant $c > 0.2604$, improving the previous best bound of $c>0.2083$ by Dumitrescu and Mandal (2020). Arr
Externí odkaz:
http://arxiv.org/abs/2402.13923
Arrangements of pseudolines are classic objects in discrete and computational geometry. They have been studied with increasing intensity since their introduction almost 100 years ago. The study of the number $B_n$ of non-isomorphic simple arrangement
Externí odkaz:
http://arxiv.org/abs/2402.13107
A \emph{saddlepoint} of an $n \times n$ matrix is an entry that is the maximum of its row and the minimum of its column. Saddlepoints give the \emph{value} of a two-player zero-sum game, corresponding to its pure-strategy Nash equilibria; efficiently
Externí odkaz:
http://arxiv.org/abs/2401.06512
Given a function $f$ from the set $[N]$ to a $d$-dimensional integer grid, we consider data structures that allow efficient orthogonal range searching queries in the image of $f$, without explicitly storing it. We show that, if $f$ is of the form $[N
Externí odkaz:
http://arxiv.org/abs/2311.12471
A saddlepoint of an $n \times n$ matrix $A$ is an entry of $A$ that is a maximum in its row and a minimum in its column. Knuth (1968) gave several different algorithms for finding a saddlepoint. The worst-case running time of these algorithms is $\Th
Externí odkaz:
http://arxiv.org/abs/2310.16801
Autor:
Dallant, Justin, Iacono, John
Consider a variant of Tetris played on a board of width $w$ and infinite height, where the pieces are axis-aligned rectangles of arbitrary integer dimensions, the pieces can only be moved before letting them drop, and a row does not disappear once it
Externí odkaz:
http://arxiv.org/abs/2202.10771
Autor:
Dallant, Justin, Iacono, John
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 either 3SUM, APSP, or the Online Matrix-Vector Multiplication proble
Externí odkaz:
http://arxiv.org/abs/2112.10095
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 red or blue, find the smallest cardinality set of axis-aligned boxes w
Externí odkaz:
http://arxiv.org/abs/2106.12969
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 setting for a certain class of algorithms A* if the following hold: - A take
Externí odkaz:
http://arxiv.org/abs/2106.05638
Autor:
Dallant, Justin, Iacono, John
Publikováno v:
In Theoretical Computer Science 21 April 2024 992
