A. Kupavskii

activity

20172025

collaborators

Showing cs.CGShow all

4 papers · 1 filter

cs.CG2025

Tree covers of size $2$ for the Euclidean plane

Artur Bikeev, Andrey Kupavskii, Maxim Turevskii

For a given metric space $(P, ϕ)$ , a tree cover of stretch $t$ is a collection of trees on $P$ such that edges $(x, y)$ of trees receive length $ϕ (x, y)$ , and such that for any pair o…

cs.CG2024

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers

Sujoy Bhore, Balázs Keszegh, Andrey Kupavskii +4

We study spanners in planar domains, including polygonal domains, polyhedral terrain, and planar metrics. Previous work showed that for any constant $ε \in (0, 1)$ , one could constru…

cs.CG2020

The VC-dimension of k-vertex d-polytopes

Andrey Kupavskii

In this short note, we show that the VC-dimension of the class of $k$ -vertex polytopes in $R^{d}$ is at most $8 d^{2} k lo g_{2} k$ , answering an old question of Long and Warmuth.

cs.CG2018

The Crossing Tverberg Theorem

Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii +2

Tverberg's theorem is one of the cornerstones of discrete geometry. It states that, given a set $X$ of at least $(d + 1) (r - 1) + 1$ points in $R^{d}$ , one can find a partition $X=…

Tree covers of size 2 for the Euclidean plane

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers

The VC-dimension of k-vertex d-polytopes

The Crossing Tverberg Theorem

Tree covers of size $2$ for the Euclidean plane