Zobrazeno 1 - 10
of 811
pro vyhledávání: '"Csaba D"'
Autor:
Akitaya, Hugo A., Biniaz, Ahmad, Demaine, Erik D., Kleist, Linda, Stock, Frederick, Tóth, Csaba D.
For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endpoint. A MinBST can be computed in $O(n\log n)$ time where $n$ is the n
Externí odkaz:
http://arxiv.org/abs/2409.11614
Euclidean spanners are important geometric objects that have been extensively studied since the 1980s. The two most basic "compactness'' measures of a Euclidean spanner $E$ are the size (number of edges) $|E|$ and the weight (sum of edge weights) $\|
Externí odkaz:
http://arxiv.org/abs/2409.08227
Autor:
Bhore, Sujoy, Keszegh, Balázs, Kupavskii, Andrey, Le, Hung, Louvet, Alexandre, Pálvölgyi, Dömötör, Tóth, Csaba D.
We study spanners in planar domains, including polygonal domains, polyhedral terrain, and planar metrics. Previous work showed that for any constant $\epsilon\in (0,1)$, one could construct a $(2+\epsilon)$-spanner with $O(n\log(n))$ edges (SICOMP 20
Externí odkaz:
http://arxiv.org/abs/2404.05045
Low-distortional metric embeddings are a crucial component in the modern algorithmic toolkit. In an online metric embedding, points arrive sequentially and the goal is to embed them into a simple space irrevocably, while minimizing the distortion. Ou
Externí odkaz:
http://arxiv.org/abs/2310.14078
Autor:
Tóth, Csaba D.
It is shown that every $n$-vertex graph that admits a 2-bend RAC drawing in the plane, where the edges are polylines with two bends per edge and any pair of edges can only cross at a right angle, has at most $20n-24$ edges for $n\geq 3$. This improve
Externí odkaz:
http://arxiv.org/abs/2308.02663
A fundamental question is whether one can maintain a maximum independent set in polylogarithmic update time for a dynamic collection of geometric objects in Euclidean space. Already, for a set of intervals, it is known that no dynamic algorithm can m
Externí odkaz:
http://arxiv.org/abs/2308.00979
Motivated by the problem of redistricting, we study area-preserving reconfigurations of connected subdivisions of a simple polygon. A connected subdivision of a polygon $\mathcal{R}$, called a district map, is a set of interior disjoint connected pol
Externí odkaz:
http://arxiv.org/abs/2307.00704
Autor:
Dumitrescu, Adrian, Tóth, Csaba D.
We introduce the Observation Route Problem ($\textsf{ORP}$) defined as follows: Given a set of $n$ pairwise disjoint compact regions in the plane, find a shortest tour (route) such that an observer walking along this tour can see (observe) some point
Externí odkaz:
http://arxiv.org/abs/2306.11522
Autor:
Dumitrescu, Adrian, Tóth, Csaba D.
For a polygon $P$ with holes in the plane, we denote by $\varrho(P)$ the ratio between the geodesic and the Euclidean diameters of $P$. It is shown that over all convex polygons with $h$~convex holes, the supremum of $\varrho(P)$ is between $\Omega(h
Externí odkaz:
http://arxiv.org/abs/2304.03484
Autor:
Eyal Ackerman, Michelle M. Allen, Gill Barequet, Maarten Löffler, Joshua Mermelstein, Diane L. Souvaine, Csaba D. Tóth
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 18 no. 3, Iss Combinatorics (2016)
We study the configuration space of rectangulations and convex subdivisions of $n$ points in the plane. It is shown that a sequence of $O(n\log n)$ elementary flip and rotate operations can transform any rectangulation to any other rectangulation on
Externí odkaz:
https://doaj.org/article/aea6f0690a3d496c9708c99db4b7571e