A. Dumitrescu

activity

20002026

most citedApproximation algorithms for TSP with neighborhoods in the plane

193 citations · 363 across the 59 of their papers we have counts for

collaborators

Showing 2014Show all

5 papers · 1 filter

math.MG2014★ 3 cited

Convex polygons in geometric triangulations

Adrian Dumitrescu, Csaba D. Tóth

We show that the maximum number of convex polygons in a triangulation of $n$ points in the plane is $O (1.502 9^{n})$ . This improves an earlier bound of $O (1.618 1^{n})$ established by va…

math.CO2014★ 5 cited

Counting Carambolas

Adrian Dumitrescu, Maarten Löffler, André Schulz +1

We give upper and lower bounds on the maximum and minimum number of geometric configurations of various kinds present (as subgraphs) in a triangulation of $n$ points in the plane.…

cs.DS2014

Selection Algorithms with Small Groups

Ke Chen, Adrian Dumitrescu

We revisit the selection problem, namely that of computing the $i$ th order statistic of $n$ given elements, in particular the classic deterministic algorithm by grouping and partit…

math.MG2014★ 2 cited

On the Total Perimeter of Homothetic Convex Bodies in a Convex Container

Adrian Dumitrescu, Csaba D. Tóth

For two planar convex bodies, $C$ and $D$ , consider a packing $S$ of $n$ positive homothets of $C$ contained in $D$ . We estimate the total perimeter of the bodies in $S$ , denoted $…

cs.DS2014

On Fence Patrolling by Mobile Agents

Adrian Dumitrescu, Anirban Ghosh, Csaba D. Tóth

Suppose that a fence needs to be protected (perpetually) by $k$ mobile agents with maximum speeds $v_{1}, \dots, v_{k}$ so that no point on the fence is left unattended for more than a…