Showing 1–43 of 43 results for author: Dumitrescu, A

Maximizing the Maximum Degree in Ordered Yao Graphs

Authors: Péter Ágoston, Adrian Dumitrescu, Arsenii Sagdeev, Karamjeet Singh, Ji Zeng

Abstract: For an ordered point set in a Euclidean space or, more generally, in an abstract metric space, the ordered Yao graph is obtained by connecting each of the points to its closest predecessor by a directed edge. We show that for every set of $n$ points in $\mathbb{R}^d$, there exists an order such that the corresponding ordered Yao graph has maximum degree at least $\log{n}/(4d)$. Apart from the… ▽ More For an ordered point set in a Euclidean space or, more generally, in an abstract metric space, the ordered Yao graph is obtained by connecting each of the points to its closest predecessor by a directed edge. We show that for every set of $n$ points in $\mathbb{R}^d$, there exists an order such that the corresponding ordered Yao graph has maximum degree at least $\log{n}/(4d)$. Apart from the $1/(4d)$ factor, this bound is the best possible. As for the abstract setting, we show that for every $n$-element metric space, there exists an order such that the corresponding ordered Yao graph has maximum degree $Ω(\sqrt{\log{n}/\log\log{n}})$. △ Less

Submitted 13 June, 2024; originally announced June 2024.

Comments: 9 pages, 1 figure

MSC Class: 05C07; 05D10; 52C10

Partitioning complete geometric graphs into plane subgraphs

Authors: Adrian Dumitrescu, János Pach

Abstract: A \emph{complete geometric graph} consists of a set $P$ of $n$ points in the plane, in general position, and all segments (edges) connecting them. It is a well known question of Bose, Hurtado, Rivera-Campo, and Wood, whether there exists a positive constant $c<1$, such that every complete geometric graph on $n$ points can be partitioned into at most $cn$ plane graphs (that is, noncrossing subgraph… ▽ More A \emph{complete geometric graph} consists of a set $P$ of $n$ points in the plane, in general position, and all segments (edges) connecting them. It is a well known question of Bose, Hurtado, Rivera-Campo, and Wood, whether there exists a positive constant $c<1$, such that every complete geometric graph on $n$ points can be partitioned into at most $cn$ plane graphs (that is, noncrossing subgraphs). We answer this question in the affirmative in the special case where the underlying point set $P$ is \emph{dense}, which means that the ratio between the maximum and the minimum distances in $P$ is of the order of $Θ(\sqrt{n})$. △ Less

Submitted 27 May, 2024; originally announced May 2024.

Comments: 10 pages, 4 figures

A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications

Authors: Adrian Dumitrescu

Abstract: We revisit the algorithmic problem of finding a triangle in a graph: We give a randomized combinatorial algorithm for triangle detection in a given $n$-vertex graph with $m$ edges running in $O(n^{7/3})$ time, or alternatively in $O(m^{4/3})$ time. This may come as a surprise since it invalidates several conjectures in the literature. In particular, - the $O(n^{7/3})$ runtime surpasses the long-… ▽ More We revisit the algorithmic problem of finding a triangle in a graph: We give a randomized combinatorial algorithm for triangle detection in a given $n$-vertex graph with $m$ edges running in $O(n^{7/3})$ time, or alternatively in $O(m^{4/3})$ time. This may come as a surprise since it invalidates several conjectures in the literature. In particular, - the $O(n^{7/3})$ runtime surpasses the long-standing fastest algorithm for triangle detection based on matrix multiplication running in $O(n^ω) = O(n^{2.372})$ time, due to Itai and Rodeh (1978). - the $O(m^{4/3})$ runtime surpasses the long-standing fastest algorithm for triangle detection in sparse graphs based on matrix multiplication running in $O(m^{2ω/(ω+1)})= O(m^{1.407})$ time due to Alon, Yuster, and Zwick (1997). - the $O(n^{7/3})$ time algorithm for triangle detection leads to a $O(n^{25/9} \log{n})$ time combinatorial algorithm for $n \times n$ Boolean matrix multiplication, by a reduction of V. V. Williams and R.~R.~Williams (2018).This invalidates a conjecture of A.~Abboud and V. V. Williams (FOCS 2014). - the $O(m^{4/3})$ runtime invalidates a conjecture of A.~Abboud and V. V. Williams (FOCS 2014) that any combinatorial algorithm for triangle detection requires $m^{3/2 - o(1)}$ time. - as a direct application of the triangle detection algorithm, we obtain a faster exact algorithm for the $k$-clique problem, surpassing an almost $40$ years old algorithm of Ne{š}et{ř}il and Poljak (1985). This result strongly disproves the combinatorial $k$-clique conjecture. - as another direct application of the triangle detection algorithm, we obtain a faster exact algorithm for the \textsc{Max-Cut} problem, surpassing an almost $20$ years old algorithm of R.~R.~Williams (2005). △ Less

Submitted 5 March, 2024; v1 submitted 1 March, 2024; originally announced March 2024.

Comments: The triangle detection algorithm may fail. The analysis of Case 2.1 (in Subsection 2.1) is invalid. Thanks to Zach Hunter for pointing this out

Two trees are better than one

Authors: Adrian Dumitrescu, János Pach, Géza Tóth

Abstract: 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 w… ▽ More 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. △ Less

Submitted 31 December, 2023; v1 submitted 15 December, 2023; originally announced December 2023.

Comments: 2 figures, 11 pages

MSC Class: 52Cxx; 05Cxx

On a Traveling Salesman Problem for Points in the Unit Cube

Authors: József Balogh, Felix Christian Clemen, Adrian Dumitrescu

Abstract: Let $X$ be an $n$-element point set in the $k$-dimensional unit cube $[0,1]^k$ where $k \geq 2$. According to an old result of Bollobás and Meir (1992), there exists a cycle (tour) $x_1, x_2, \ldots, x_n$ through the $n$ points, such that $\left(\sum_{i=1}^n |x_i - x_{i+1}|^k \right)^{1/k} \leq c_k$, where $|x-y|$ is the Euclidean distance between $x$ and $y$, and $c_k$ is an absolute constant tha… ▽ More Let $X$ be an $n$-element point set in the $k$-dimensional unit cube $[0,1]^k$ where $k \geq 2$. According to an old result of Bollobás and Meir (1992), there exists a cycle (tour) $x_1, x_2, \ldots, x_n$ through the $n$ points, such that $\left(\sum_{i=1}^n |x_i - x_{i+1}|^k \right)^{1/k} \leq c_k$, where $|x-y|$ is the Euclidean distance between $x$ and $y$, and $c_k$ is an absolute constant that depends only on $k$, where $x_{n+1} \equiv x_1$. From the other direction, for every $k \geq 2$ and $n \geq 2$, there exist $n$ points in $[0,1]^k$, such that their shortest tour satisfies $\left(\sum_{i=1}^n |x_i - x_{i+1}|^k \right)^{1/k} = 2^{1/k} \cdot \sqrt{k}$. For the plane, the best constant is $c_2=2$ and this is the only exact value known. Bollob{á}s and Meir showed that one can take $c_k = 9 \left(\frac23 \right)^{1/k} \cdot \sqrt{k}$ for every $k \geq 3$ and conjectured that the best constant is $c_k = 2^{1/k} \cdot \sqrt{k}$, for every $k \geq 2$. Here we significantly improve the upper bound and show that one can take $c_k = 3 \sqrt5 \left(\frac23 \right)^{1/k} \cdot \sqrt{k}$ or $c_k = 2.91 \sqrt{k} \ (1+o_k(1))$. Our bounds are constructive. We also show that $c_3 \geq 2^{7/6}$, which disproves the conjecture for $k=3$. Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás--Meir conjecture is proposed. △ Less

Submitted 2 July, 2024; v1 submitted 4 October, 2023; originally announced October 2023.

Maximal Distortion of Geodesic Diameters in Polygonal Domains

Authors: Adrian Dumitrescu, Csaba D. Tóth

Abstract: 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 $Ω(h^{1/3})$ and $O(h^{1/2})$. The upper bound improves to $O(1+\min\{h^{3/4}Δ,h^{1/2}Δ^{1/2}\})$ if every hole has diameter at most $Δ\cdot {\rm diam}_2(P)$;… ▽ More 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 $Ω(h^{1/3})$ and $O(h^{1/2})$. The upper bound improves to $O(1+\min\{h^{3/4}Δ,h^{1/2}Δ^{1/2}\})$ if every hole has diameter at most $Δ\cdot {\rm diam}_2(P)$; and to $O(1)$ if every hole is a \emph{fat} convex polygon. Furthermore, we show that the function $g(h)=\sup_P \varrho(P)$ over convex polygons with $h$ convex holes has the same growth rate as an analogous quantity over geometric triangulations with $h$ vertices when $h\rightarrow \infty$. △ Less

Submitted 19 May, 2023; v1 submitted 7 April, 2023; originally announced April 2023.

Comments: 15 pages, 4 figures, to appear in the Proceedings of the 34th International Workshop on Combinatorial Algorithms (IWOCA 2023)

Almost Congruent Triangles

Authors: József Balogh, Felix Christian Clemen, Adrian Dumitrescu

Abstract: Almost $50$ years ago Erdős and Purdy asked the following question: Given $n$ points in the plane, how many triangles can be approximate congruent to equilateral triangles? They pointed out that by dividing the points evenly into three small clusters built around the three vertices of a fixed equilateral triangle, one gets at least… ▽ More Almost $50$ years ago Erdős and Purdy asked the following question: Given $n$ points in the plane, how many triangles can be approximate congruent to equilateral triangles? They pointed out that by dividing the points evenly into three small clusters built around the three vertices of a fixed equilateral triangle, one gets at least $\left\lfloor \frac{n}{3} \right\rfloor \cdot \left\lfloor \frac{n+1}{3} \right\rfloor \cdot \left\lfloor \frac{n+2}{3} \right\rfloor$ such approximate copies. In this paper we provide a matching upper bound and thereby answer their question. More generally, for every triangle $T$ we determine the maximum number of approximate congruent triangles to $T$ in a point set of size $n$. Parts of our proof are based on hypergraph Turán theory: for each point set in the plane and a triangle $T$, we construct a $3$-uniform hypergraph $\mathcal{H}=\mathcal{H}(T)$, which contains no hypergraph as a subgraph from a family of forbidden hypergraphs $\mathcal{F}=\mathcal{F}(T)$. Our upper bound on the number of edges of $\mathcal{H}$ will determine the maximum number of triangles that are approximate congruent to $T$. △ Less

Submitted 26 March, 2023; originally announced March 2023.

Two-sided convexity testing with certificates

Authors: Adrian Dumitrescu

Abstract: We revisit the problem of property testing for convex position for point sets in $\mathbb{R}^d$. Our results draw from previous ideas of Czumaj, Sohler, and Ziegler (ESA 2000). First, the algorithm is redesigned and its analysis is revised for correctness. Second, its functionality is expanded by (i)~exhibiting both negative and positive certificates along with the convexity determination, and (ii… ▽ More We revisit the problem of property testing for convex position for point sets in $\mathbb{R}^d$. Our results draw from previous ideas of Czumaj, Sohler, and Ziegler (ESA 2000). First, the algorithm is redesigned and its analysis is revised for correctness. Second, its functionality is expanded by (i)~exhibiting both negative and positive certificates along with the convexity determination, and (ii)~significantly extending the input range for moderate and higher dimensions. The behavior of the randomized tester is as follows: (i)~if $P$ is in convex position, it accepts; (ii)~if $P$ is far from convex position, with probability at least $2/3$, it rejects and outputs a $(d+2)$-point witness of non-convexity as a negative certificate; (iiii)~if $P$ is close to convex position, with probability at least $2/3$, it accepts and outputs an approximation of the largest subset in convex position. The algorithm examines a sublinear number of points and runs in subquadratic time for every dimension $d$. △ Less

Submitted 7 May, 2023; v1 submitted 14 February, 2023; originally announced February 2023.

Comments: 15 pages, 2 figures

Peeling Sequences

Authors: Adrian Dumitrescu, Géza Tóth

Abstract: Given a set of $n$ labeled points in general position in the plane, we remove all of its points one by one. At each step, one point from the convex hull of the remaining set is erased. In how many ways can the process be carried out? The answer obviously depends on the point set. If the points are in convex position, there are exactly $n!$ ways, which is the maximum number of ways for $n$ points.… ▽ More Given a set of $n$ labeled points in general position in the plane, we remove all of its points one by one. At each step, one point from the convex hull of the remaining set is erased. In how many ways can the process be carried out? The answer obviously depends on the point set. If the points are in convex position, there are exactly $n!$ ways, which is the maximum number of ways for $n$ points. But what is the minimum number? It is shown that this number is (roughly) at least $3^n$ and at most $12.29^n$. △ Less

Submitted 22 March, 2023; v1 submitted 10 November, 2022; originally announced November 2022.

Comments: new co-author; improved upper bound; 10 pages, 2 figures

Finding Points in Convex Position in Density-Restricted Sets

Authors: Adrian Dumitrescu, Csaba D. Tóth

Abstract: For a finite set $A\subset \mathbb{R}^d$, let $Δ(A)$ denote the spread of $A$, which is the ratio of the maximum pairwise distance to the minimum pairwise distance. For a positive integer $n$, let $γ_d(n)$ denote the largest integer such that any set $A$ of $n$ points in general position in $\mathbb{R}^d$, satisfying $Δ(A) \leq αn^{1/d}$ for a fixed $α>0$, contains at least $γ_d(n)$ points in conv… ▽ More For a finite set $A\subset \mathbb{R}^d$, let $Δ(A)$ denote the spread of $A$, which is the ratio of the maximum pairwise distance to the minimum pairwise distance. For a positive integer $n$, let $γ_d(n)$ denote the largest integer such that any set $A$ of $n$ points in general position in $\mathbb{R}^d$, satisfying $Δ(A) \leq αn^{1/d}$ for a fixed $α>0$, contains at least $γ_d(n)$ points in convex position. About $30$ years ago, Valtr proved that $γ_2(n)=Θ(n^{1/3})$. Since then no further results have been obtained in higher dimensions. Here we continue this line of research in three dimensions and prove that $γ_3(n) =Θ(n^{1/2})$. The lower bound implies the following approximation: Given any $n$-element point set $A\subset \mathbb{R}^3$ in general position, satisfying $Δ(A) \leq αn^{1/3}$ for a fixed $α$, a $Ω(n^{-1/6})$-factor approximation of the maximum-size convex subset of points can be computed by a randomized algorithm in $O(n \log{n})$ expected time. △ Less

Submitted 18 December, 2022; v1 submitted 6 May, 2022; originally announced May 2022.

Comments: 20 pages, 6 figures

Lattice and Non-lattice Piercing of Axis-Parallel Rectangles: Exact Algorithms and a Separation Result

Authors: Adrian Dumitrescu, Josef Tkadlec

Abstract: For a given family of shapes ${\mathcal F}$ in the plane, we study what is the lowest possible density of a point set $P$ that pierces ("intersects", "hits") all translates of each shape in ${\mathcal F}$. For instance, if ${\mathcal F}$ consists of two axis-parallel rectangles the best known piercing set, i.e., one with the lowest density, is a lattice: for certain families the known lattices are… ▽ More For a given family of shapes ${\mathcal F}$ in the plane, we study what is the lowest possible density of a point set $P$ that pierces ("intersects", "hits") all translates of each shape in ${\mathcal F}$. For instance, if ${\mathcal F}$ consists of two axis-parallel rectangles the best known piercing set, i.e., one with the lowest density, is a lattice: for certain families the known lattices are provably optimal whereas for other, those lattices are just the best piercing sets currently known. Given a finite family ${\mathcal F}$ of axis-parallel rectangles, we present two algorithms for finding an optimal ${\mathcal F}$-piercing lattice. Both algorithms run in time polynomial in the number of rectangles and the maximum aspect ratio of the rectangles in the family. No prior algorithms were known for this problem. Then we prove that for every $n \geq 3$, there exist a family of $n$ axis-parallel rectangles for which the best piercing density achieved by a lattice is separated by a positive (constant) gap from the optimal piercing density for the respective family. Finally, we sharpen our separation result by running the first algorithm on a suitable instance, and show that the best lattice can be sometimes worse by $20\%$ than the optimal piercing set. △ Less

Submitted 21 April, 2022; originally announced April 2022.

Comments: 26 pages, 13 figures

The Dirac--Goodman--Pollack Conjecture

Authors: Adrian Dumitrescu

Abstract: 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… ▽ More 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. △ Less

Submitted 28 August, 2022; v1 submitted 12 April, 2022; originally announced April 2022.

Comments: 14 pages, 4 figures

On a two-player transversal game on a square grid

Authors: Adrian Dumitrescu

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

Submitted 15 January, 2021; v1 submitted 11 January, 2021; originally announced January 2021.

Comments: The rules of the game were misinterpreted. The short analysis does not stand

On the Shortest Separating Cycle

Authors: Adrian Dumitrescu

Abstract: According to a result of Arkin~\etal~(2016), given $n$ point pairs in the plane, there exists a simple polygonal cycle that separates the two points in each pair to different sides; moreover, a $O(\sqrt{n})$-factor approximation with respect to the minimum length can be computed in polynomial time. Here the following results are obtained: (I)~We extend the problem to geometric hypergraphs and ob… ▽ More According to a result of Arkin~\etal~(2016), given $n$ point pairs in the plane, there exists a simple polygonal cycle that separates the two points in each pair to different sides; moreover, a $O(\sqrt{n})$-factor approximation with respect to the minimum length can be computed in polynomial time. Here the following results are obtained: (I)~We extend the problem to geometric hypergraphs and obtain the following characterization of feasibility. Given a geometric hypergraph on points in the plane with hyperedges of size at least $2$, there exists a simple polygonal cycle that separates each hyperedge if and only if the hypergraph is $2$-colorable. (II)~We extend the $O(\sqrt{n})$-factor approximation in the length measure as follows: Given a geometric graph $G=(V,E)$, a separating cycle (if it exists) can be computed in $O(m+ n\log{n})$ time, where $|V|=n$, $|E|=m$. Moreover, a $O(\sqrt{n})$-approximation of the shortest separating cycle can be found in polynomial time. Given a geometric graph $G=(V,E)$ in $\mathbb{R}^3$, a separating polyhedron (if it exists) can be found in $O(m+ n\log{n})$ time, where $|V|=n$, $|E|=m$. Moreover, a $O(n^{2/3})$-approximation of a separating polyhedron of minimum perimeter can be found in polynomial time. (III)~Given a set of $n$ point pairs in convex position in the plane, we show that a $(1+\varepsilon)$-approximation of a shortest separating cycle can be computed in time $n^{O(\varepsilon^{-1/2})}$. In this regard, we prove a lemma on convex polygon approximation that is of independent interest. △ Less

Submitted 3 December, 2019; originally announced December 2019.

Comments: 12 pages, 7 figures; to appear in CGTA

Finding a Mediocre Player

Authors: Adrian Dumitrescu

Abstract: Consider a totally ordered set $S$ of $n$ elements; as an example, a set of tennis players and their rankings. Further assume that their ranking is a total order and thus satisfies transitivity and anti-symmetry. Following Frances Yao (1974), an element (player) is said to be $(i,j)$-\emph{mediocre} if it is neither among the top $i$ nor among the bottom $j$ elements of $S$. Finding a mediocre ele… ▽ More Consider a totally ordered set $S$ of $n$ elements; as an example, a set of tennis players and their rankings. Further assume that their ranking is a total order and thus satisfies transitivity and anti-symmetry. Following Frances Yao (1974), an element (player) is said to be $(i,j)$-\emph{mediocre} if it is neither among the top $i$ nor among the bottom $j$ elements of $S$. Finding a mediocre element is closely related to finding the median element. More than $40$ years ago, Yao suggested a very simple and elegant algorithm for finding an $(i,j)$-mediocre element: Pick $i+j+1$ elements arbitrarily and select the $(i+1)$-th largest among them. She also asked: "Is this the best algorithm?" No one seems to have found a better algorithm ever since. We first provide a deterministic algorithm that beats the worst-case comparison bound in Yao's algorithm for a large range of values of $i$ (and corresponding suitable $j=j(i)$) even if the current best selection algorithm is used. We then repeat the exercise for randomized algorithms; the average number of comparisons of our algorithm beats the average comparison bound in Yao's algorithm for another large range of values of $i$ (and corresponding suitable $j=j(i)$) even if the best selection algorithm is used; the improvement is most notable in the symmetric case $i=j$. Moreover, the tight bound obtained in the analysis of Yao's algorithm allows us to give a definite answer for this class of algorithms. In summary, we answer Yao's question as follows: (i)~"Presently not" for deterministic algorithms and (ii)~"Definitely not" for randomized algorithms. (In fairness, it should be said however that Yao posed the question in the context of deterministic algorithms.) △ Less

Submitted 14 November, 2020; v1 submitted 25 January, 2019; originally announced January 2019.

Comments: 15 pages, 4 figures

New Lower Bounds for the Number of Pseudoline Arrangements

Authors: Adrian Dumitrescu, Ritankar Mandal

Abstract: Arrangements of lines and pseudolines are fundamental objects in discrete and computational geometry. They also appear in other areas of computer science, such as the study of sorting networks. Let $B_n$ be the number of nonisomorphic arrangements of $n$ pseudolines and let $b_n=\log_2{B_n}$. The problem of estimating $B_n$ was posed by Knuth in 1992. Knuth conjectured that… ▽ More Arrangements of lines and pseudolines are fundamental objects in discrete and computational geometry. They also appear in other areas of computer science, such as the study of sorting networks. Let $B_n$ be the number of nonisomorphic arrangements of $n$ pseudolines and let $b_n=\log_2{B_n}$. The problem of estimating $B_n$ was posed by Knuth in 1992. Knuth conjectured that $b_n \leq {n \choose 2} + o(n^2)$ and also derived the first upper and lower bounds: $b_n \leq 0.7924 (n^2 +n)$ and $b_n \geq n^2/6 -O(n)$. The upper bound underwent several improvements, $b_n \leq 0.6988\, n^2$ (Felsner, 1997), and $b_n \leq 0.6571\, n^2$ (Felsner and Valtr, 2011), for large $n$. Here we show that $b_n \geq cn^2 -O(n \log{n})$ for some constant $c>0.2083$. In particular, $b_n \geq 0.2083\, n^2$ for large $n$. This improves the previous best lower bound, $b_n \geq 0.1887\, n^2$, due to Felsner and Valtr (2011). Our arguments are elementary and geometric in nature. Further, our constructions are likely to spur new developments and improved lower bounds for related problems, such as in topological graph drawings. △ Less

Submitted 7 December, 2018; v1 submitted 10 September, 2018; originally announced September 2018.

Comments: 29 pages, 16 figures, 11 tables

On the Longest Spanning Tree with Neighborhoods

Authors: Ke Chen, Adrian Dumitrescu

Abstract: 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 pro… ▽ More 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. △ Less

Submitted 28 April, 2020; v1 submitted 8 December, 2017; originally announced December 2017.

Comments: 12 pages, 4 figures. Section 2 is split into three subsections; more technical details are provided in section 3

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

Authors: Adrian Dumitrescu, Minghui Jiang

Abstract: 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… ▽ More 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. △ Less

Submitted 13 October, 2016; v1 submitted 24 August, 2016; originally announced August 2016.

Comments: 14 pages, 1 figure; updated bibliography and note added at the end of Section 7

Monotone Paths in Geometric Triangulations

Authors: Adrian Dumitrescu, Ritankar Mandal, Csaba D. Tóth

Abstract: (I) We prove that the (maximum) number of monotone paths in a geometric triangulation of $n$ points in the plane is $O(1.7864^n)$. This improves an earlier upper bound of $O(1.8393^n)$; the current best lower bound is $Ω(1.7003^n)$. (II) Given a planar geometric graph $G$ with $n$ vertices, we show that the number of monotone paths in $G$ can be computed in $O(n^2)$ time. (I) We prove that the (maximum) number of monotone paths in a geometric triangulation of $n$ points in the plane is $O(1.7864^n)$. This improves an earlier upper bound of $O(1.8393^n)$; the current best lower bound is $Ω(1.7003^n)$. (II) Given a planar geometric graph $G$ with $n$ vertices, we show that the number of monotone paths in $G$ can be computed in $O(n^2)$ time. △ Less

Submitted 3 October, 2016; v1 submitted 16 August, 2016; originally announced August 2016.

Comments: 50 pages, 35 figures

A Selectable Sloppy Heap

Authors: Adrian Dumitrescu

Abstract: We study the selection problem, namely that of computing the $i$th order statistic of $n$ given elements. Here we offer a data structure called \emph{selectable sloppy heap} handling a dynamic version in which upon request: (i)~a new element is inserted or (ii)~an element of a prescribed quantile group is deleted from the data structure. Each operation is executed in (ideal!) constant time---and i… ▽ More We study the selection problem, namely that of computing the $i$th order statistic of $n$ given elements. Here we offer a data structure called \emph{selectable sloppy heap} handling a dynamic version in which upon request: (i)~a new element is inserted or (ii)~an element of a prescribed quantile group is deleted from the data structure. Each operation is executed in (ideal!) constant time---and is thus independent of $n$ (the number of elements stored in the data structure)---provided that the number of quantile groups is fixed. This is the first result of this kind accommodating both insertion and deletion in constant time. As such, our data structure outperforms the soft heap data structure of Chazelle (which only offers constant amortized complexity for a fixed error rate $0<\varepsilon \leq 1/2$) in applications such as dynamic percentile maintenance. The design demonstrates how slowing down a certain computation can speed up the data structure. △ Less

Submitted 9 August, 2017; v1 submitted 26 July, 2016; originally announced July 2016.

Comments: 13 pages

Anchored Rectangle and Square Packings

Authors: Kevin Balas, Adrian Dumitrescu, Csaba D. Tóth

Abstract: 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 rectangl… ▽ More 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. △ Less

Submitted 29 February, 2016; originally announced March 2016.

Comments: 33 pages, 20 figures

Lattice spanners of low degree

Authors: Adrian Dumitrescu, Anirban Ghosh

Abstract: 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 la… ▽ More 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$. △ Less

Submitted 21 April, 2016; v1 submitted 13 February, 2016; originally announced February 2016.

Comments: 17 pages, 13 figures; A preliminary version in: Proceedings of the 2nd International Conference on Algorithms and Discrete Applied Mathematics, Thiruvananthapuram, India, Febr. 2016, vol $9602$ of LNCS

Lower bounds on the dilation of plane spanners

Authors: Adrian Dumitrescu, Anirban Ghosh

Abstract: (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 spa… ▽ More (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$. △ Less

Submitted 21 April, 2016; v1 submitted 23 September, 2015; originally announced September 2015.

Comments: Revised definitions in the introduction; 23 pages, 15 figures; 2 tables

Problems on Track Runners

Authors: Adrian Dumitrescu, Csaba D. Tóth

Abstract: Consider the circle $C$ of length 1 and a circular arc $A$ of length $\ell\in (0,1)$. It is shown that there exists $k=k(\ell) \in \mathbb{N}$, and a schedule for $k$ runners along the circle with $k$ constant but distinct positive speeds so that at any time $t \geq 0$, at least one of the $k$ runners is not in $A$. On the other hand, we show the following: Assume that $k$ runners… ▽ More Consider the circle $C$ of length 1 and a circular arc $A$ of length $\ell\in (0,1)$. It is shown that there exists $k=k(\ell) \in \mathbb{N}$, and a schedule for $k$ runners along the circle with $k$ constant but distinct positive speeds so that at any time $t \geq 0$, at least one of the $k$ runners is not in $A$. On the other hand, we show the following: Assume that $k$ runners $1,2,\ldots,k$, with constant rationally independent (thus distinct) speeds $ξ_1,ξ_2,\ldots,ξ_k$, run clockwise along a circle of length $1$, starting from arbitrary points. For every circular arc $A\subset C$ and for every $T>0$, there exists $t>T$ such that all runners are in $A$ at time $t$. Several other problems of a similar nature are investigated. △ Less

Submitted 2 November, 2017; v1 submitted 28 August, 2015; originally announced August 2015.

Comments: 9 pages, 1 figure

Convex polygons in geometric triangulations

Authors: Adrian Dumitrescu, Csaba D. Tóth

Abstract: We show that the maximum number of convex polygons in a triangulation of $n$ points in the plane is $O(1.5029^n)$. This improves an earlier bound of $O(1.6181^n)$ established by van Kreveld, Löffler, and Pach (2012) and almost matches the current best lower bound of $Ω(1.5028^n)$ due to the same authors. Given a planar straight-line graph $G$ with $n$ vertices, we show how to compute efficiently t… ▽ More We show that the maximum number of convex polygons in a triangulation of $n$ points in the plane is $O(1.5029^n)$. This improves an earlier bound of $O(1.6181^n)$ established by van Kreveld, Löffler, and Pach (2012) and almost matches the current best lower bound of $Ω(1.5028^n)$ due to the same authors. Given a planar straight-line graph $G$ with $n$ vertices, we show how to compute efficiently the number of convex polygons in $G$. △ Less

Submitted 16 February, 2017; v1 submitted 4 November, 2014; originally announced November 2014.

Comments: 20 pages, 6 figures, a preliminary version has been presented at WADS 2015

MSC Class: 05C85; 05D99; 52A10; 68W05

Journal ref: Combinatorics, Probability and Computing 26(5) (2017), 641-659

Counting Carambolas

Authors: Adrian Dumitrescu, Maarten Löffler, André Schulz, Csaba D. Tóth

Abstract: 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. 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. △ Less

Submitted 20 September, 2015; v1 submitted 6 October, 2014; originally announced October 2014.

Comments: update reflects journal version, to appear in Graphs and Combinatorics; 18 pages, 13 figures

Selection Algorithms with Small Groups

Authors: Ke Chen, Adrian Dumitrescu

Abstract: 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 partition due to Blum, Floyd, Pratt, Rivest, and Tarjan (1973). Whereas the original algorithm uses groups of odd size at least $5$ and runs in linear time, it has been perpetuated in the literature that using smaller group si… ▽ More 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 partition due to Blum, Floyd, Pratt, Rivest, and Tarjan (1973). Whereas the original algorithm uses groups of odd size at least $5$ and runs in linear time, it has been perpetuated in the literature that using smaller group sizes will force the worst-case running time to become superlinear, namely $Ω(n \log{n})$. We first point out that the usual arguments found in the literature justifying the superlinear worst-case running time fall short of proving this claim. We further prove that it is possible to use group size smaller than $5$ while maintaining the worst case linear running time. To this end we introduce three simple variants of the classic algorithm, the repeated step algorithm, the shifting target algorithm, and the hyperpair algorithm, all running in linear time. △ Less

Submitted 5 April, 2019; v1 submitted 11 September, 2014; originally announced September 2014.

Comments: 13 pages, 5 figures, 1 table

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

Authors: Adrian Dumitrescu, Csaba D. Tóth

Abstract: 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… ▽ More 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. △ Less

Submitted 15 May, 2014; originally announced May 2014.

Comments: A preliminary version of this paper appeared in Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2013), Berkeley, CA, 2013, LNCS~8096, pp. 96--109

Journal ref: Beiträge zur Algebra und Geometrie 56 (2) (2015), 515-532

On Fence Patrolling by Mobile Agents

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

Abstract: 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 \e… ▽ More 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. △ Less

Submitted 23 January, 2014; originally announced January 2014.

Comments: 13 pages, 6 figures

The opaque square

Authors: Adrian Dumitrescu, Minghui Jiang

Abstract: 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… ▽ More 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. △ Less

Submitted 13 November, 2013; originally announced November 2013.

Comments: 23 pages, 8 figures

The traveling salesman problem for lines, balls and planes

Authors: Adrian Dumitrescu, Csaba D. Tóth

Abstract: 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… ▽ More 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. △ Less

Submitted 24 November, 2015; v1 submitted 26 March, 2013; originally announced March 2013.

Comments: 30 pages, 9 figures; final version to appear in ACM Transactions on Algorithms

Covering Paths for Planar Point Sets

Authors: Adrian Dumitrescu, Daniel Gerbner, Balazs Keszegh, Csaba D. Toth

Abstract: 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 con… ▽ More 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. △ Less

Submitted 1 March, 2013; originally announced March 2013.

Comments: 19 pages, 7 figures

The traveling salesman problem for lines and rays in the plane

Authors: Adrian Dumitrescu

Abstract: 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,… ▽ More 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$. △ Less

Submitted 26 April, 2012; originally announced April 2012.

Comments: 10 pages, 5 figures

Disjoint empty disks supported by a point set

Authors: Adrian Dumitrescu, Minghui Jiang

Abstract: 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. 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. △ Less

Submitted 27 July, 2012; v1 submitted 2 March, 2012; originally announced March 2012.

Comments: 19 pages, 8 figures; minor update; updated references

MSC Class: 52C10 ACM Class: F.2.2

Packing anchored rectangles

Authors: Adrian Dumitrescu, Csaba D. Tóth

Abstract: 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 rectang… ▽ More 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. △ Less

Submitted 30 July, 2012; v1 submitted 25 July, 2011; originally announced July 2011.

Comments: 17 pages, 7 figures; updated references

Coloring translates and homothets of a convex body

Authors: Adrian Dumitrescu, Minghui Jiang

Abstract: 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$. 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$. △ Less

Submitted 7 August, 2010; originally announced August 2010.

Comments: 11 pages, 2 figures

Approximate Euclidean Ramsey theorems

Authors: Adrian Dumitrescu

Abstract: 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 l… ▽ More 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. △ Less

Submitted 9 April, 2010; originally announced April 2010.

Comments: 11 pages, 1 figure.

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

Authors: Adrian Dumitrescu, Minghui Jiang, Csaba D. Tóth

Abstract: 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. Fr… ▽ More 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. △ Less

Submitted 1 February, 2010; originally announced February 2010.

Comments: 13 pages, 2 figures. An earlier version (now obsolete): A. Dumitrescu and Cs. D. Tóth: New bounds on the average distance from the Fermat-Weber center of a planar convex body, in Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC 2009), 2009, LNCS 5878, Springer, pp. 132-141

Metric inequalities for polygons

Authors: Adrian Dumitrescu

Abstract: 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 p… ▽ More 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. △ Less

Submitted 21 June, 2012; v1 submitted 19 December, 2009; originally announced December 2009.

Comments: 13 pages, 2 figures. This version replaces the previous version from 8 Feb 2011. A new section has been added and the material has been reorganized; a correction has been done in the proof of Lemma 4 (analysis of Case 3)

Extremal problems on triangle areas in two and three dimensions

Authors: Adrian Dumitrescu, Micha Sharir, Csaba D. Toth

Abstract: 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… ▽ More 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. △ Less

Submitted 22 October, 2007; originally announced October 2007.

Comments: title page + 27 pages, 5 figures

MSC Class: 52C10; 52C45; 05D99

Journal ref: J. Combin. Theory Ser. A 116 (2009), 1177-1198

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

Authors: Csaba D. Toth, Adrian Dumitrescu

Abstract: 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 algorith… ▽ More 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)$. △ Less

Submitted 19 October, 2007; originally announced October 2007.

Comments: 19 pages, 3 figures, a preliminary version has appeard in proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2007

MSC Class: 52C10; 52C35; 05D99

Journal ref: Combinatorics Probability and Computing 17 (2008), 203-224

Compatible Geometric Matchings

Authors: Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, Mikio Kano, Alberto Márquez, David Rappaport, Shakhar Smorodinsky, Diane Souvaine, Jorge Urrutia, David R. Wood

Abstract: This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are \emph{compatible} if they have the same vertex set and their union is also non-crossing. Our first result states that for any two perfect matchings $M$ and $M'$ of the same set of $n$ points, for some $k\in\Oh{\log n}$, there is a sequence of perfect matchings $M=M_0,M_1,...,M_k=M'$, such that each $M_i$… ▽ More This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are \emph{compatible} if they have the same vertex set and their union is also non-crossing. Our first result states that for any two perfect matchings $M$ and $M'$ of the same set of $n$ points, for some $k\in\Oh{\log n}$, there is a sequence of perfect matchings $M=M_0,M_1,...,M_k=M'$, such that each $M_i$ is compatible with $M_{i+1}$. This improves the previous best bound of $k\leq n-2$. We then study the conjecture: \emph{every perfect matching with an even number of edges has an edge-disjoint compatible perfect matching}. We introduce a sequence of stronger conjectures that imply this conjecture, and prove the strongest of these conjectures in the case of perfect matchings that consist of vertical and horizontal segments. Finally, we prove that every perfect matching with $n$ edges has an edge-disjoint compatible matching with approximately $4n/5$ edges. △ Less

Submitted 16 January, 2008; v1 submitted 21 September, 2007; originally announced September 2007.

Comments: improved exposition and improved results

MSC Class: 52C99

Journal ref: Computational Geometry: Theory & Applications 42(6-7):617-626, 2009.

On the geometric dilation of closed curves, graphs, and point sets

Authors: Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein, Günter Rote

Abstract: The detour between two points u and v (on edges or vertices) of an embedded planar graph whose edges are curves is the ratio between the shortest path in in the graph between u and v and their Euclidean distance. The maximum detour over all pairs of points is called the geometric dilation. Ebbers-Baumann, Gruene and Klein have shown that every finite point set is contained in a planar graph whos… ▽ More The detour between two points u and v (on edges or vertices) of an embedded planar graph whose edges are curves is the ratio between the shortest path in in the graph between u and v and their Euclidean distance. The maximum detour over all pairs of points is called the geometric dilation. Ebbers-Baumann, Gruene and Klein have shown that every finite point set is contained in a planar graph whose geometric dilation is at most 1.678, and some point sets require graphs with dilation at least pi/2 = 1.57... We prove a stronger lower bound of 1.00000000001*pi/2 by relating graphs with small dilation to a problem of packing and covering the plane by circular disks. The proof relies on halving pairs, pairs of points dividing a given closed curve C in two parts of equal length, and their minimum and maximum distances h and H. Additionally, we analyze curves of constant halving distance (h=H), examine the relation of h to other geometric quantities and prove some new dilation bounds. △ Less

Submitted 25 August, 2005; v1 submitted 8 July, 2004; originally announced July 2004.

Comments: 31 pages, 16 figures. The new version is the extended journal submission; it includes additional material from a conference submission (ref. [6] in the paper)

MSC Class: 51F99

Journal ref: Computational Geometry, Theory and Applications 36 (2006), 16-38