Zobrazeno 1 - 10
of 429
pro vyhledávání: '"CHAN, TIMOTHY M."'
The hypergraph Zarankiewicz's problem, introduced by Erd\H{o}s in 1964, asks for the maximum number of hyperedges in an $r$-partite hypergraph with $n$ vertices in each part that does not contain a copy of $K_{t,t,\ldots,t}$. Erd\H{o}s obtained a nea
Externí odkaz:
http://arxiv.org/abs/2412.06490
Autor:
Bhore, Sujoy, Chan, Timothy M.
We develop simple and general techniques to obtain faster (near-linear time) static approximation algorithms, as well as efficient dynamic data structures, for four fundamental geometric optimization problems: minimum piercing set (MPS), maximum inde
Externí odkaz:
http://arxiv.org/abs/2407.20659
Autor:
Chan, Timothy M., Hair, Isaac M.
We revisit a standard polygon containment problem: given a convex $k$-gon $P$ and a convex $n$-gon $Q$ in the plane, find a placement of $P$ inside $Q$ under translation and rotation (if it exists), or more generally, find the largest copy of $P$ ins
Externí odkaz:
http://arxiv.org/abs/2403.13292
Polynomial partitioning techniques have recently led to improved geometric data structures for a variety of fundamental problems related to semialgebraic range searching and intersection searching in 3D and higher dimensions (e.g., see [Agarwal, Aron
Externí odkaz:
http://arxiv.org/abs/2403.12303
Let $X$ be a set of points in $\mathbb{R}^2$ and $\mathcal{O}$ be a set of geometric objects in $\mathbb{R}^2$, where $|X| + |\mathcal{O}| = n$. We study the problem of computing a minimum subset $\mathcal{O}^* \subseteq \mathcal{O}$ that encloses al
Externí odkaz:
http://arxiv.org/abs/2402.17322
Autor:
Bhore, Sujoy, Chan, Timothy M.
In this work, we study two fundamental graph optimization problems, minimum vertex cover (MVC) and maximum-cardinality matching (MCM), for intersection graphs of geometric objects, e.g., disks, rectangles, hypercubes, etc., in $d$-dimensional Euclide
Externí odkaz:
http://arxiv.org/abs/2402.07441
Autor:
Chan, Timothy M., Huang, Zhengcheng
We present the first fully dynamic connectivity data structures for geometric intersection graphs achieving constant query time and sublinear amortized update time for most types of geometric objects in 2D. Our data structures can answer connectivity
Externí odkaz:
http://arxiv.org/abs/2402.05357
We present the first optimal randomized algorithm for constructing the order-$k$ Voronoi diagram of $n$ points in two dimensions. The expected running time is $O(n\log n + nk)$, which improves the previous, two-decades-old result of Ramos (SoCG'99) b
Externí odkaz:
http://arxiv.org/abs/2310.15363
We study the classic Text-to-Pattern Hamming Distances problem: given a pattern $P$ of length $m$ and a text $T$ of length $n$, both over a polynomial-size alphabet, compute the Hamming distance between $P$ and $T[i\, .\, . \, i+m-1]$ for every shift
Externí odkaz:
http://arxiv.org/abs/2310.13174
Autor:
Chan, Timothy M., Xu, Yinzhan
In this paper, we provide simpler reductions from Exact Triangle to two important problems in fine-grained complexity: Exact Triangle with Few Zero-Weight $4$-Cycles and All-Edges Sparse Triangle. Exact Triangle instances with few zero-weight $4$-cyc
Externí odkaz:
http://arxiv.org/abs/2310.11575