Source author record

Adrian Dumitrescu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry math.CO Discrete Mathematics math.MG Data Structures and Algorithms Computational Complexity

Catalog footprint

Research overview

33works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

On the Stretch Factor of Polygonal Chains

Let $P=(p_1, p_2, \dots, p_n)$ be a polygonal chain in $\mathbb{R}^d$ . The stretch factor of $P$ is the ratio between the total length of $P$ and the distance of its endpoints, $\sum_{i = 1}^{n-1} |p_i p_{i+1}|/|p_1 p_n|$ . For a parameter $c \geq 1$ , we call $P$ a $c$ -chain if $|p_ip_j|+|p_jp_k| \leq c|p_ip_k|$ , for every triple $(i,j,k)$ , $1 \leq i<j<k \leq n$ . The stretch factor is a global property: it measures how close $P$ is to a straight line, and it involves all the vertices of $P$ ; being a $c$ -chain, on the other hand, is a fingerprint-property: it only depends on subsets of $O(1)$ vertices of the chain. We investigate how the $c$ -chain property influences the stretch factor in the plane: (i) we show that for every $\varepsilon > 0$ , there is a noncrossing $c$ -chain that has stretch factor $Ω(n^{1/2-\varepsilon})$ , for sufficiently large constant $c=c(\varepsilon)$ ; (ii) on the other hand, the stretch factor of a $c$ -chain $P$ is $O\left(n^{1/2}\right)$ , for every constant $c\geq 1$ , regardless of whether $P$ is crossing or noncrossing; and (iii) we give a randomized algorithm that can determine, for a polygonal chain $P$ in $\mathbb{R}^2$ with $n$ vertices, the minimum $c\geq 1$ for which $P$ is a $c$ -chain in $O\left(n^{2.5}\ \mathrm{polylog}\ n\right)$ expected time and $O(n\log n)$ space. These results generalize to $\mathbb{R}^d$ . For every dimension $d\geq 2$ and every $\varepsilon>0$ , we construct a noncrossing $c$ -chain that has stretch factor $Ω\left(n^{(1-\varepsilon)(d-1)/d}\right)$ ; on the other hand, the stretch factor of any $c$ -chain is $O\left((n-1)^{(d-1)/d}\right)$ ; for every $c>1$ , we can test whether an $n$ -vertex chain in $\mathbb{R}^d$ is a $c$ -chain in $O\left(n^{3-1/d}\ \mathrm{polylog}\ n\right)$ expected time and $O(n\log n)$ space.

preprint2023arXiv

Two trees are better than one

We consider partitions of a point set into two parts, and the lengths of the minimum spanning trees of the original set and of the two parts. If $w(P)$ denotes the length of a minimum spanning tree of $P$ , we show that every set $P$ of $n \geq 12$ points admits a bipartition $P= R \cup B$ for which the ratio $\frac{w(R)+w(B)}{w(P)}$ is strictly larger than $1$ ; and that $1$ is the largest number with this property. Furthermore, we provide a very fast algorithm that computes such a bipartition in $O(1)$ time and one that computes the corresponding ratio in $O(n \log{n})$ time. In certain settings, a ratio larger than $1$ can be expected and sometimes guaranteed. For example, if $P$ is a set of $n$ random points uniformly distributed in $[0,1]^2$ ( $n \to \infty$ ), then for any $\eps>0$, the above ratio in a maximizing partition is at least $\sqrt2 -\eps$ with probability tending to $1$ . As another example, if $P$ is a set of $n$ points with spread at most $α\sqrt{n}$ , for some constant $α>0$ , then the aforementioned ratio in a maximizing partition is $1 + Ω(α^{-2})$ . All our results and techniques are extendable to higher dimensions.

preprint2022arXiv

The Dirac--Goodman--Pollack Conjecture

In one of their seminal articles on allowable sequences, Goodman and Pollack gave combinatorial generalizations for three problems in discrete geometry, one of which being the Dirac conjecture. According to this conjecture, any set of $n$ noncollinear points in the plane has a point incident to at least $c n$ connecting lines determined by the set. The notion of allowable sequences of permutations provides a natural combinatorial setting for analyzing these problems. Within this formalism, the conjectured generalization reads as follows: \emph{Any nontrivial allowable $n$ -sequence $Σ$ has a local sequence $Λ_i$ whose half-period is at least $c n$ .} The conjecture is confirmed here with a concrete bound $c=1/845$ . Several related problems are discussed.

preprint2021arXiv

On a two-player transversal game on a square grid

We give a short analysis of the \emph{transversal achievement game} on a square grid due to M. Erickson (2010).

preprint2021arXiv

Sparse Hop Spanners for Unit Disk Graphs

A unit disk graph $G$ on a given set $P$ of points in the plane is a geometric graph where an edge exists between two points $p,q \in P$ if and only if $|pq| \leq 1$ . A spanning subgraph $G'$ of $G$ is a $k$ -hop spanner if and only if for every edge $pq\in G$ , there is a path between $p,q$ in $G'$ with at most $k$ edges. We obtain the following results for unit disk graphs in the plane. (I) Every $n$ -vertex unit disk graph has a $5$ -hop spanner with at most $5.5n$ edges. We analyze the family of spanners constructed by Biniaz (2020) and improve the upper bound on the number of edges from $9n$ to $5.5n$ . (II) Using a new construction, we show that every $n$ -vertex unit disk graph has a $3$ -hop spanner with at most $11n$ edges. (III) Every $n$ -vertex unit disk graph has a $2$ -hop spanner with $O(n\log n)$ edges. This is the first nontrivial construction of $2$ -hop spanners. (IV) For every sufficiently large positive integer $n$ , there exists a set $P$ of $n$ points on a circle, such that every plane hop spanner on $P$ has hop stretch factor at least $4$ . Previously, no lower bound greater than $2$ was known. (V) For every finite point set on a circle, there exists a plane (i.e., crossing-free) $4$ -hop spanner. As such, this provides a tight bound for points on a circle. (VI) The maximum degree of $k$ -hop spanners cannot be bounded from above by a function of $k$ for any positive integer $k$ .

preprint2020arXiv

Multiparty Selection

Given a sequence $A$ of $n$ numbers and an integer (target) parameter $1\leq i\leq n$ , the (exact) selection problem asks to find the $i$ -th smallest element in $A$ . An element is said to be $(i,j)$ -mediocre if it is neither among the top $i$ nor among the bottom $j$ elements of $S$ . The approximate selection problem asks to find a $(i,j)$ -mediocre element for some given $i,j$ ; as such, this variant allows the algorithm to return any element in a prescribed range. In the first part, we revisit the selection problem in the two-party model introduced by Andrew Yao (1979) and then extend our study of exact selection to the multiparty model. In the second part, we deduce some communication complexity benefits that arise in approximate selection. In particular, we present a deterministic protocol for finding an approximate median among $k$ players.

preprint2020arXiv

On the Longest Spanning Tree with Neighborhoods

We study a maximization problem for geometric network design. Given a set of $n$ compact neighborhoods in $\mathbb{R}^d$ , select a point in each neighborhood, so that the longest spanning tree on these points (as vertices) has maximum length. Here we give an approximation algorithm with ratio $0.511$ , which represents the first, albeit small, improvement beyond $1/2$ . While we suspect that the problem is NP-hard already in the plane, this issue remains open.

preprint2016arXiv

Anchored Rectangle and Square Packings

For points $p_1,\ldots , p_n$ in the unit square $[0,1]^2$ , an \emph{anchored rectangle packing} consists of interior-disjoint axis-aligned empty rectangles $r_1,\ldots , r_n\subseteq [0,1]^2$ such that point $p_i$ is a corner of the rectangle $r_i$ (that is, $r_i$ is \emph{anchored} at $p_i$ ) for $i=1,\ldots, n$ . We show that for every set of $n$ points in $[0,1]^2$ , there is an anchored rectangle packing of area at least $7/12-O(1/n)$ , and for every $n\in \mathbf{N}$ , there are point sets for which the area of every anchored rectangle packing is at most $2/3$ . The maximum area of an anchored \emph{square} packing is always at least $5/32$ and sometimes at most $7/27$ . The above constructive lower bounds immediately yield constant-factor approximations, of $7/12 -\varepsilon$ for rectangles and $5/32$ for squares, for computing anchored packings of maximum area in $O(n\log n)$ time. We prove that a simple greedy strategy achieves a $9/47$ -approximation for anchored square packings, and $1/3$ for lower-left anchored square packings. Reductions to maximum weight independent set (MWIS) yield a QPTAS and a PTAS for anchored rectangle and square packings in $n^{O(1/\varepsilon)}$ and $\exp({\rm poly}(\log (n/\varepsilon)))$ time, respectively.

preprint2016arXiv

Constant-Factor Approximation for TSP with Disks

We revisit the traveling salesman problem with neighborhoods (TSPN) and present the first constant-ratio approximation for disks in the plane: Given a set of $n$ disks in the plane, a TSP tour whose length is at most $O(1)$ times the optimal can be computed in time that is polynomial in $n$ . Our result is the first constant-ratio approximation for a class of planar convex bodies of arbitrary size and arbitrary intersections. In order to achieve a $O(1)$ -approximation, we reduce the traveling salesman problem with disks, up to constant factors, to a minimum weight hitting set problem in a geometric hypergraph. The connection between TSPN and hitting sets in geometric hypergraphs, established here, is likely to have future applications.

preprint2016arXiv

Lattice spanners of low degree

Let $δ_0(P,k)$ denote the degree $k$ dilation of a point set $P$ in the domain of plane geometric spanners. If $Λ$ is the infinite square lattice, it is shown that $1+\sqrt{2} \leq δ_0(Λ,3) \leq (3+2\sqrt2) \, 5^{-1/2} = 2.6065\ldots$ and $δ_0(Λ,4) = \sqrt{2}$ . If $Λ$ is the infinite hexagonal lattice, it is shown that $δ_0(Λ,3) = 1+\sqrt{3}$ and $δ_0(Λ,4) = 2$ . All our constructions are planar lattice tilings constrained to degree $3$ or $4$ .

preprint2016arXiv

Lower bounds on the dilation of plane spanners

(I) We exhibit a set of 23 points in the plane that has dilation at least $1.4308$ , improving the previously best lower bound of $1.4161$ for the worst-case dilation of plane spanners. (II) For every integer $n\geq13$ , there exists an $n$ -element point set $S$ such that the degree 3 dilation of $S$ denoted by $δ_0(S,3) \text{ equals } 1+\sqrt{3}=2.7321\ldots$ in the domain of plane geometric spanners. In the same domain, we show that for every integer $n\geq6$ , there exists a an $n$ -element point set $S$ such that the degree 4 dilation of $S$ denoted by $δ_0(S,4) \text{ equals } 1 + \sqrt{(5-\sqrt{5})/2}=2.1755\ldots$ The previous best lower bound of $1.4161$ holds for any degree. (III) For every integer $n\geq6$ , there exists an $n$ -element point set $S$ such that the stretch factor of the greedy triangulation of $S$ is at least $2.0268$ .

preprint2016arXiv

Perfect vector sets, properly overlapping partitions, and largest empty box

We revisit the following problem (along with its higher dimensional variant): Given a set $S$ of $n$ points inside an axis-parallel rectangle $U$ in the plane, find a maximum-area axis-parallel sub-rectangle that is contained in $U$ but contains no points of $S$ . (I) We present an algorithm that finds a large empty box amidst $n$ points in $[0,1]^d$ : a box whose volume is at least $\frac{\log{d}}{4(n + \log{d})}$ can be computed in $O(n+d \log{d})$ time. (II) To better analyze the above approach, we introduce the concepts of perfect vector sets and properly overlapping partitions, in connection to the minimum volume of a maximum empty box amidst $n$ points in the unit hypercube $[0,1]^d$ , and derive bounds on their sizes.

preprint2015arXiv

Counting Carambolas

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. Configurations of interest include \emph{convex polygons}, \emph{star-shaped polygons} and \emph{monotone paths}. We also consider related problems for \emph{directed} planar straight-line graphs.

preprint2015arXiv

The traveling salesman problem for lines, balls and planes

We revisit the traveling salesman problem with neighborhoods (TSPN) and propose several new approximation algorithms. These constitute either first approximations (for hyperplanes, lines, and balls in $\mathbb{R}^d$ , for $d\geq 3$ ) or improvements over previous approximations achievable in comparable times (for unit disks in the plane). \smallskip (I) Given a set of $n$ hyperplanes in $\mathbb{R}^d$ , a TSP tour whose length is at most $O(1)$ times the optimal can be computed in $O(n)$ time, when $d$ is constant. \smallskip (II) Given a set of $n$ lines in $\mathbb{R}^d$ , a TSP tour whose length is at most $O(\log^3 n)$ times the optimal can be computed in polynomial time for all $d$ . \smallskip (III) Given a set of $n$ unit balls in $\mathbb{R}^d$ , a TSP tour whose length is at most $O(1)$ times the optimal can be computed in polynomial time, when $d$ is constant.

preprint2014arXiv

Minimum Convex Partitions and Maximum Empty Polytopes

Let $S$ be a set of $n$ points in $\mathbb{R}^d$ . A Steiner convex partition is a tiling of ${\rm conv}(S)$ with empty convex bodies. For every integer $d$ , we show that $S$ admits a Steiner convex partition with at most $\lceil (n-1)/d\rceil$ tiles. This bound is the best possible for points in general position in the plane, and it is best possible apart from constant factors in every fixed dimension $d\geq 3$ . We also give the first constant-factor approximation algorithm for computing a minimum Steiner convex partition of a planar point set in general position. Establishing a tight lower bound for the maximum volume of a tile in a Steiner convex partition of any $n$ points in the unit cube is equivalent to a famous problem of Danzer and Rogers. It is conjectured that the volume of the largest tile is $ω(1/n)$ . Here we give a $(1-\varepsilon)$ -approximation algorithm for computing the maximum volume of an empty convex body amidst $n$ given points in the $d$ -dimensional unit box $[0,1]^d$ .

preprint2014arXiv

On Fence Patrolling by Mobile Agents

Suppose that a fence needs to be protected (perpetually) by $k$ mobile agents with maximum speeds $v_1,\ldots,v_k$ so that no point on the fence is left unattended for more than a given amount of time. The problem is to determine if this requirement can be met, and if so, to design a suitable patrolling schedule for the agents. Alternatively, one would like to find a schedule that minimizes the \emph{idle time}, that is, the longest time interval during which some point is not visited by any agent. We revisit this problem, introduced by Czyzowicz et al.(2011), and discuss several strategies for the cases where the fence is an open and a closed curve, respectively. In particular: (i) we disprove a conjecture by Czyzowicz et al. regarding the optimality of their Algorithm ${\mathcal A_2}$ for unidirectional patrolling of a closed fence; (ii) we present an algorithm with a lower idle time for patrolling an open fence, improving an earlier result of Kawamura and Kobayashi.

preprint2014arXiv

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

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 ${\rm per}(S)$ , in terms of ${\rm per}(D)$ and $n$ . When all homothets of $C$ touch the boundary of the container $D$ , we show that either ${\rm per}(S)=O(\log n)$ or ${\rm per}(S)=O(1)$ , depending on how $C$ and $D$ "fit together," and these bounds are the best possible apart from the constant factors. Specifically, we establish an optimal bound ${\rm per}(S)=O(\log n)$ unless $D$ is a convex polygon and every side of $D$ is parallel to a corresponding segment on the boundary of $C$ (for short, $D$ is \emph{parallel to} $C$ ). When $D$ is parallel to $C$ but the homothets of $C$ may lie anywhere in $D$ , we show that ${\rm per}(S)=O((1+{\rm esc}(S)) \log n/\log \log n)$ , where ${\rm esc}(S)$ denotes the total distance of the bodies in $S$ from the boundary of $D$ . Apart from the constant factor, this bound is also the best possible.

preprint2013arXiv

Covering Paths for Planar Point Sets

Given $n$ points in the plane, a \emph{covering path} is a polygonal path that visits all the points. If no three points are collinear, every covering path requires at least $n/2$ segments, and $n-1$ straight line segments obviously suffice even if the covering path is required to be noncrossing. We show that every set of $n$ points in the plane admits a (possibly self-crossi ng) covering path consisting of $n/2 +O(n/\log{n})$ straight line segments. If the path is required to be noncrossing, we prove that $(1-\eps)n$ straight line segments suffice for a small constant $\eps>0$, and we exhibit $n$ -element point sets that require at least $5n/9 -O(1)$ segments in every such path. Further, the analogous question for noncrossing \emph{covering trees} is considered and similar bounds are obtained. Finally, it is shown that computing a noncrossing covering path for $n$ points in the plane requires $Ω(n \log{n})$ time in the worst case.

preprint2013arXiv

The opaque square

The problem of finding small sets that block every line passing through a unit square was first considered by Mazurkiewicz in 1916. We call such a set {\em opaque} or a {\em barrier} for the square. The shortest known barrier has length $\sqrt{2}+ \frac{\sqrt{6}}{2}= 2.6389\ldots$ . The current best lower bound for the length of a (not necessarily connected) barrier is $2$ , as established by Jones about 50 years ago. No better lower bound is known even if the barrier is restricted to lie in the square or in its close vicinity. Under a suitable locality assumption, we replace this lower bound by $2+10^{-12}$ , which represents the first, albeit small, step in a long time toward finding the length of the shortest barrier. A sharper bound is obtained for interior barriers: the length of any interior barrier for the unit square is at least $2 + 10^{-5}$ . Two of the key elements in our proofs are: (i) formulas established by Sylvester for the measure of all lines that meet two disjoint planar convex bodies, and (ii) a procedure for detecting lines that are witness to the invalidity of a short bogus barrier for the square.

preprint2012arXiv

Disjoint empty disks supported by a point set

For a planar point-set $P$ , let D(P) be the minimum number of pairwise-disjoint empty disks such that each point in $P$ lies on the boundary of some disk. Further define D(n) as the maximum of D(P) over all n-element point sets. Hosono and Urabe recently conjectured that $D(n)=\lceil n/2 \rceil$ . Here we show that $D(n) \geq n/2 + n/236 - O(\sqrt{n})$ and thereby disprove this conjecture.

preprint2012arXiv

Metric inequalities for polygons

Let $A_1,A_2,...,A_n$ be the vertices of a polygon with unit perimeter, that is $\sum_{i=1}^n |A_i A_{i+1}|=1$ . We derive various tight estimates on the minimum and maximum values of the sum of pairwise distances, and respectively sum of pairwise squared distances among its vertices. In most cases such estimates on these sums in the literature were known only for convex polygons. In the second part, we turn to a problem of Braß regarding the maximum perimeter of a simple $n$ -gon ( $n$ odd) contained in a disk of unit radius. The problem was solved by Audet et al. \cite{AHM09b}, who gave an exact formula. Here we present an alternative simpler proof of this formula. We then examine what happens if the simplicity condition is dropped, and obtain an exact formula for the maximum perimeter in this case as well.

preprint2012arXiv

Opaque sets

The problem of finding "small" sets that meet every straight-line which intersects a given convex region was initiated by Mazurkiewicz in 1916. We call such a set an {\em opaque set} or a {\em barrier} for that region. We consider the problem of computing the shortest barrier for a given convex polygon with $n$ vertices. No exact algorithm is currently known even for the simplest instances such as a square or an equilateral triangle. For general barriers, we present an approximation algorithm with ratio $1/2 + \frac{2 +\sqrt{2}}π=1.5867...$ . For connected barriers we achieve the approximation ratio 1.5716, while for single-arc barriers we achieve the approximation ratio $\frac{π+5}{π+2} = 1.5834...$ . All three algorithms run in O(n) time. We also show that if the barrier is restricted to the (interior and the boundary of the) input polygon, then the problem admits a fully polynomial-time approximation scheme for the connected case and a quadratic-time exact algorithm for the single-arc case.

preprint2012arXiv

Packing anchored rectangles

Let $S$ be a set of $n$ points in the unit square $[0,1]^2$ , one of which is the origin. We construct $n$ pairwise interior-disjoint axis-aligned empty rectangles such that the lower left corner of each rectangle is a point in $S$ , and the rectangles jointly cover at least a positive constant area (about 0.09). This is a first step towards the solution of a longstanding conjecture that the rectangles in such a packing can jointly cover an area of at least 1/2.

preprint2012arXiv

The traveling salesman problem for lines and rays in the plane

In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of $n$ regions (neighborhoods) and we seek a shortest tour that visits each region. In the path variant, we seek a shortest path that visits each region. We present several linear-time approximation algorithms with improved ratios for these problems for two cases of neighborhoods that are (infinite) lines, and respectively, (half-infinite) rays. Along the way we derive a tight bound on the minimum perimeter of a rectangle enclosing an open curve of length $L$ .

preprint2011arXiv

Bounds on the maximum multiplicity of some common geometric graphs

We obtain new lower and upper bounds for the maximum multiplicity of some weighted and, respectively, non-weighted common geometric graphs drawn on n points in the plane in general position (with no three points collinear): perfect matchings, spanning trees, spanning cycles (tours), and triangulations. (i) We present a new lower bound construction for the maximum number of triangulations a set of n points in general position can have. In particular, we show that a generalized double chain formed by two almost convex chains admits Ω(8.65^n) different triangulations. This improves the bound Ω(8.48^n) achieved by the double zig-zag chain configuration studied by Aichholzer et al. (ii) We present a new lower bound of Ω(12.00^n) for the number of non-crossing spanning trees of the double chain composed of two convex chains. The previous bound, Ω(10.42^n), stood unchanged for more than 10 years. (iii) Using a recent upper bound of 30^n for the number of triangulations, due to Sharir and Sheffer, we show that n points in the plane in general position admit at most O(68.62^n) non-crossing spanning cycles. (iv) We derive lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). We show that the number of shortest non-crossing tours can be exponential in n. Likewise, we show that both the number of longest non-crossing tours and the number of longest non-crossing perfect matchings can be exponential in n. Moreover, we show that there are sets of n points in convex position with an exponential number of longest non-crossing spanning trees. For points in convex position we obtain tight bounds for the number of longest and shortest tours. We give a combinatorial characterization of the longest tours, which leads to an O(nlog n) time algorithm for computing them.

preprint2011arXiv

Sweeping an oval to a vanishing point

Given a convex region in the plane, and a sweep-line as a tool, what is best way to reduce the region to a single point by a sequence of sweeps? The problem of sweeping points by orthogonal sweeps was first studied in [2]. Here we consider the following \emph{slanted} variant of sweeping recently introduced in [1]: In a single sweep, the sweep-line is placed at a start position somewhere in the plane, then moved continuously according to a sweep vector $\vec v$ (not necessarily orthogonal to the sweep-line) to another parallel end position, and then lifted from the plane. The cost of a sequence of sweeps is the sum of the lengths of the sweep vectors. The (optimal) sweeping cost of a region is the infimum of the costs over all finite sweeping sequences for that region. An optimal sweeping sequence for a region is one with a minimum total cost, if it exists. Another parameter of interest is the number of sweeps. We show that there exist convex regions for which the optimal sweeping cost cannot be attained by two sweeps. This disproves a conjecture of Bousany, Karker, O'Rourke, and Sparaco stating that two sweeps (with vectors along the two adjacent sides of a minimum-perimeter enclosing parallelogram) always suffice [1]. Moreover, we conjecture that for some convex regions, no finite sweeping sequence is optimal. On the other hand, we show that both the 2-sweep algorithm based on minimum-perimeter enclosing rectangle and the 2-sweep algorithm based on minimum-perimeter enclosing parallelogram achieve a $4/π\approx 1.27$ approximation in this sweeping model.

preprint2010arXiv

Approximate Euclidean Ramsey theorems

According to a classical result of Szemerédi, every dense subset of $1,2,...,N$ contains an arbitrary long arithmetic progression, if $N$ is large enough. Its analogue in higher dimensions due to Fürstenberg and Katznelson says that every dense subset of $\{1,2,...,N\}^d$ contains an arbitrary large grid, if $N$ is large enough. Here we generalize these results for separated point sets on the line and respectively in the Euclidean space: (i) every dense separated set of points in some interval $[0,L]$ on the line contains an arbitrary long approximate arithmetic progression, if $L$ is large enough. (ii) every dense separated set of points in the $d$ -dimensional cube $[0,L]^d$ in $\RR^d$ contains an arbitrary large approximate grid, if $L$ is large enough. A further generalization for any finite pattern in $\RR^d$ is also established. The separation condition is shown to be necessary for such results to hold. In the end we show that every sufficiently large point set in $\RR^d$ contains an arbitrarily large subset of almost collinear points. No separation condition is needed in this case.

preprint2010arXiv

Coloring translates and homothets of a convex body

We obtain improved upper bounds and new lower bounds on the chromatic number as a linear function of the clique number, for the intersection graphs (and their complements) of finite families of translates and homothets of a convex body in $\RR^n$.

preprint2010arXiv

Dispersion in disks

We present three new approximation algorithms with improved constant ratios for selecting $n$ points in $n$ disks such that the minimum pairwise distance among the points is maximized. (1) A very simple $O(n\log n)$ -time algorithm with ratio $0.511$ for disjoint unit disks. (2) An LP-based algorithm with ratio $0.707$ for disjoint disks of arbitrary radii that uses a linear number of variables and constraints, and runs in polynomial time. (3) A hybrid algorithm with ratio either $0.4487$ or $0.4674$ for (not necessarily disjoint) unit disks that uses an algorithm of Cabello in combination with either the simple $O(n\log n)$ -time algorithm or the LP-based algorithm. The LP algorithm can be extended for disjoint balls of arbitrary radii in $\RR^d$, for any (fixed) dimension $d$ , while preserving the features of the planar algorithm. The algorithm introduces a novel technique which combines linear programming and projections for approximating Euclidean distances. The previous best approximation ratio for dispersion in disjoint disks, even when all disks have the same radius, was $1/2$ . Our results give a partial answer to an open question raised by Cabello, who asked whether the ratio $1/2$ could be improved.

preprint2010arXiv

Long non-crossing configurations in the plane

We revisit several maximization problems for geometric networks design under the non-crossing constraint, first studied by Alon, Rajagopalan and Suri (ACM Symposium on Computational Geometry, 1993). Given a set of $n$ points in the plane in general position (no three points collinear), compute a longest non-crossing configuration composed of straight line segments that is: (a) a matching (b) a Hamiltonian path (c) a spanning tree. Here we obtain new results for (b) and (c), as well as for the Hamiltonian cycle problem: (i) For the longest non-crossing Hamiltonian path problem, we give an approximation algorithm with ratio $\frac{2}{π+1} \approx 0.4829$ . The previous best ratio, due to Alon et al., was $1/π\approx 0.3183$ . Moreover, the ratio of our algorithm is close to $2/π$ on a relatively broad class of instances: for point sets whose perimeter (or diameter) is much shorter than the maximum length matching. The algorithm runs in $O(n^{7/3}\log{n})$ time. (ii) For the longest non-crossing spanning tree problem, we give an approximation algorithm with ratio 0.502 which runs in $O(n \log{n})$ time. The previous ratio, 1/2, due to Alon et al., was achieved by a quadratic time algorithm. Along the way, we first re-derive the result of Alon et al. with a faster $O(n \log{n})$ -time algorithm and a very simple analysis. (iii) For the longest non-crossing Hamiltonian cycle problem, we give an approximation algorithm whose ratio is close to $2/π$ on a relatively broad class of instances: for point sets with the product $\bf{<}$ diameter $\times$ convex hull size $\bf{>}$ much smaller than the maximum length matching. The algorithm runs in $O(n^{7/3}\log{n})$ time. No previous approximation results were known for this problem.

preprint2010arXiv

New bounds on the average distance from the Fermat-Weber center of a planar convex body

The Fermat-Weber center of a planar body $Q$ is a point in the plane from which the average distance to the points in $Q$ is minimal. We first show that for any convex body $Q$ in the plane, the average distance from the Fermat-Weber center of $Q$ to the points of $Q$ is larger than ${1/6} \cdot Δ(Q)$ , where $Δ(Q)$ is the diameter of $Q$ . This proves a conjecture of Carmi, Har-Peled and Katz. From the other direction, we prove that the same average distance is at most $\frac{2(4-\sqrt3)}{13} \cdot Δ(Q) < 0.3490 \cdot Δ(Q)$ . The new bound substantially improves the previous bound of $\frac{2}{3 \sqrt3} \cdot Δ(Q) \approx 0.3849 \cdot Δ(Q)$ due to Abu-Affash and Katz, and brings us closer to the conjectured value of ${1/3} \cdot Δ(Q)$ . We also confirm the upper bound conjecture for centrally symmetric planar convex bodies.

preprint2007arXiv

Extremal problems on triangle areas in two and three dimensions

The study of extremal problems on triangle areas was initiated in a series of papers by Erdős and Purdy in the early 1970s. In this paper we present new results on such problems, concerning the number of triangles of the same area that are spanned by finite point sets in the plane and in 3-space, and the number of distinct areas determined by the triangles. In the plane, our main result is an $O(n^{44/19}) =O(n^{2.3158})$ upper bound on the number of unit-area triangles spanned by $n$ points, which is the first breakthrough improving the classical bound of $O(n^{7/3})$ from 1992. We also make progress in a number of important special cases: We show that (i) For points in convex position, there exist $n$ -element point sets that span $Ω(n\log n)$ triangles of unit area. (ii) The number of triangles of minimum (nonzero) area determined by $n$ points is at most ${2/3}(n^2-n)$ ; there exist $n$ -element point sets (for arbitrarily large $n$ ) that span $(6/π^2-o(1))n^2$ minimum-area triangles. (iii) The number of acute triangles of minimum area determined by $n$ points is O(n); this is asymptotically tight. (iv) For $n$ points in convex position, the number of triangles of minimum area is O(n); this is asymptotically tight. (v) If no three points are allowed to be collinear, there are $n$ -element point sets that span $Ω(n\log n)$ minimum-area triangles (in contrast to (ii), where collinearities are allowed and a quadratic lower bound holds). In 3-space we prove an $O(n^{17/7}β(n))= O(n^{2.4286})$ upper bound on the number of unit-area triangles spanned by $n$ points, where $β(n)$ is an extremely slowly growing function related to the inverse Ackermann function. The best previous bound, $O(n^{8/3})$ , is an old result from 1971.

preprint2007arXiv

On the number of tetrahedra with minimum, unit, and distinct volumes in three-space

We formulate and give partial answers to several combinatorial problems on volumes of simplices determined by $n$ points in 3-space, and in general in $d$ dimensions. (i) The number of tetrahedra of minimum (nonzero) volume spanned by $n$ points in $\RR^3$ is at most ${2/3}n^3-O(n^2)$ , and there are point sets for which this number is ${3/16}n^3-O(n^2)$ . We also present an $O(n^3)$ time algorithm for reporting all tetrahedra of minimum nonzero volume, and thereby extend an algorithm of Edelsbrunner, O'Rourke, and Seidel. In general, for every $k,d\in \NN$, $1\leq k \leq d$ , the maximum number of $k$ -dimensional simplices of minimum (nonzero) volume spanned by $n$ points in $\RR^d$ is $Θ(n^k)$ . (ii) The number of unit-volume tetrahedra determined by $n$ points in $\RR^3$ is $O(n^{7/2})$ , and there are point sets for which this number is $Ω(n^3 \log \log{n})$ . (iii) For every $d\in \NN$, the minimum number of distinct volumes of all full-dimensional simplices determined by $n$ points in $\RR^d$, not all on a hyperplane, is $Θ(n)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Adrian Dumitrescu

Research overview

Is this your work?

33 publications

On the Stretch Factor of Polygonal Chains

Two trees are better than one

The Dirac--Goodman--Pollack Conjecture

On a two-player transversal game on a square grid

Sparse Hop Spanners for Unit Disk Graphs

Multiparty Selection

On the Longest Spanning Tree with Neighborhoods

Anchored Rectangle and Square Packings

Constant-Factor Approximation for TSP with Disks

Lattice spanners of low degree

Lower bounds on the dilation of plane spanners

Perfect vector sets, properly overlapping partitions, and largest empty box

Counting Carambolas

The traveling salesman problem for lines, balls and planes

Minimum Convex Partitions and Maximum Empty Polytopes

On Fence Patrolling by Mobile Agents

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

Covering Paths for Planar Point Sets

The opaque square

Disjoint empty disks supported by a point set

Metric inequalities for polygons

Opaque sets

Packing anchored rectangles

The traveling salesman problem for lines and rays in the plane

Bounds on the maximum multiplicity of some common geometric graphs

Sweeping an oval to a vanishing point

Approximate Euclidean Ramsey theorems

Coloring translates and homothets of a convex body

Dispersion in disks

Long non-crossing configurations in the plane

New bounds on the average distance from the Fermat-Weber center of a planar convex body

Extremal problems on triangle areas in two and three dimensions

On the number of tetrahedra with minimum, unit, and distinct volumes in three-space

See the researcher in context

Building this map preview