Adrian Dumitrescu

A Couple of Simple Algorithms for $k$ -Dispersion

Ke Chen, Adrian Dumitrescu

Given a set $P$ of $n$ points in $R^{d}$ , and a positive integer $k \leq n$ , the $k$ -dispersion problem is that of selecting $k$ of the given points so that the minimum inte…

Note on the Number of Almost Ordinary Triangles

Adrian Dumitrescu, János Pach

Let $X$ be a set of $n$ points in the plane, not all on a line. According to the Gallai-Sylvester theorem, $X$ always spans an \emph{ordinary line}, i.e., one that passes through p…

Arcs with increasing chords in $R^{d}$

Adrian Dumitrescu, Zsolt Lángi

A curve $γ$ that connects $s$ and $t$ has the increasing chord property if $∣ b c ∣ \leq ∣ a d ∣$ whenever $a, b, c, d$ lie in that order on $γ$ . For planar curves, the length of such a cur…

The number of regular simplices in higher dimensions

Felix Christian Clemen, Adrian Dumitrescu, Dingyuan Liu

We study the extremal function $S_{d}^{k} (n)$ , defined as the maximum number of regular $(k - 1)$ -simplices spanned by $n$ points in $R^{d}$ . For any fixed $d \geq 2 k \geq 6$ , we dete…

Covering Complete Geometric Graphs by Monotone Paths

Adrian Dumitrescu, János Pach, Morteza Saghafian +1

Given a set $A$ of $n$ points (vertices) in general position in the plane, the \emph{complete geometric graph} $K_{n} [A]$ consists of all $(2 n)$ segments (edges) between the…

math.MG2025

Closed curve covering and multiagent TSP ratios

Travis Dillon, Adrian Dumitrescu

How efficiently can a closed curve of unit length in $R^{d}$ be covered by $k$ closed curves so as to minimize the maximum length of the $k$ curves? We show that the maximum…

On multiplicities of interpoint distances

Felix Christian Clemen, Adrian Dumitrescu, Dingyuan Liu

Given a set $X \subseteq R^{2}$ of $n$ points and a distance $d > 0$ , the multiplicity of $d$ is the number of times the distance $d$ appears between points in $X$ . Let $a_1(X)…

General Position Subset Selection in Line Arrangements

Adrian Dumitrescu

Given a set of points in the plane, the \textsc{General Position Subset Selection} problem is that of finding a maximum-size subset of points in general position, i.e., with no thr…

cs.CR2025

TrustZero -- open, verifiable and scalable zero-trust

Adrian-Tudor Dumitrescu, Johan Pouwelse

We present a passport-level trust token for Europe. In an era of escalating cyber threats fueled by global competition in economic, military, and technological domains, traditional…

A Purely Geometric Variant of the Gale-Berlekamp Switching Game

Adrian Dumitrescu, Jeck Lim, János Pach +1

We introduce the following variant of the Gale-Berlekamp switching game. Let $P$ be a set of n noncollinear points in the plane, each of them having weight $+ 1$ or $- 1$ . At each st…

Geometric Variants of the Gale--Berlekamp Switching Game

Adrian Dumitrescu

The Gale-Berlekamp switching game is played on the following device: $G_{n} = {1, 2, \dots, n} \times {1, 2, \dots, n}$ is an $n \times n$ array of lights is controlled by $2 n$ switche…

Subset selection problems in planar point sets

József Balogh, Felix Christian Clemen, Adrian Dumitrescu +1

Given a finite point set satisfying condition $A$ , the subset selection problem asks, how large of a subset satisfying condition $B$ can be extracted? In this p…

cs.DM2024

A Stopping Game on Zero-Sum Sequences

Adrian Dumitrescu, Arsenii Sagdeev

We introduce and analyze a natural game formulated as follows. In this one-person game, the player is given a random permutation $A = (a_{1}, \dots, a_{n})$ of a multiset $M$ of $n$ reals…

Maximizing the Maximum Degree in Ordered Nearest Neighbor Graphs

Péter Ágoston, Adrian Dumitrescu, Arsenii Sagdeev +2

For an ordered point set in a Euclidean space or, more generally, in an abstract metric space, the ordered Nearest Neighbor Graph is obtained by connecting each of the points to it…