Zobrazeno 1 - 10
of 256
pro vyhledávání: '"Iacono, John"'
An $\ell$-vertex-ranking of a graph $G$ is a colouring of the vertices of $G$ with integer colours so that in any connected subgraph $H$ of $G$ with diameter at most $\ell$, there is a vertex in $H$ whose colour is larger than that of every other ver
Externí odkaz:
http://arxiv.org/abs/2404.16340
Autor:
Haeupler, Bernhard, Hladík, Richard, Iacono, John, Rozhon, Vaclav, Tarjan, Robert, Tětek, Jakub
We consider the problem of sorting $n$ items, given the outcomes of $m$ pre-existing comparisons. We present a simple, natural deterministic algorithm that runs in $O(m+\log T)$ time and does $O(\log T)$ comparisons, where $T$ is the number of total
Externí odkaz:
http://arxiv.org/abs/2404.04552
Autor:
Collette, Sébastien, Iacono, John
Dijkstra's algorithm is the standard method for computing shortest paths on arbitrary graphs. However, it is slow for large graphs, taking at least linear time. It has been long known that for real world road networks, creating a hierarchy of well-ch
Externí odkaz:
http://arxiv.org/abs/2312.04235
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
The $B^{\epsilon}$-tree [Brodal and Fagerberg 2003] is a simple I/O-efficient external-memory-model data structure that supports updates orders of magnitude faster than B-tree with a query performance comparable to the B-tree: for any positive consta
Externí odkaz:
http://arxiv.org/abs/2211.06044
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
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: Given two sets $A$, $B$, each consisting of $n$ pairwise disjoint segmen
Externí odkaz:
http://arxiv.org/abs/2109.07587
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 constant-factor approximate maximum independent set for broad classes of fat
Externí odkaz:
http://arxiv.org/abs/2108.08050
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 that transforms one realizer into another. Two types of flips in a reali
Externí odkaz:
http://arxiv.org/abs/2106.14451