Adrian Dumitrescu, Micha Sharir, Csaba D. Tóth
problems on triangle areas in two and three dimensions ∗
Piercing translates and homothets of a convex body (2009)
Dumitrescu, Adrian, Jiang, Minghui
According to a classical result of Gr\"unbaum, the transversal number $\tau(\F)$ of any family $\F$ of pairwise-intersecting translates or homothets of a convex body $C$ in $\RR^d$ is bounded by a...
Long non-crossing configurations in the plane (2009)
Dumitrescu, Adrian, Tóth, Csaba D.
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)....
On the largest empty axis-parallel box amidst $n$ points (2009)
Dumitrescu, Adrian, Jiang, Minghui
We give the first nontrivial upper and lower bounds on the maximum volume of an empty axis-parallel box inside an axis-parallel unit hypercube in $\RR^d$ containing $n$ points. For a fixed $d$, we...
Minimum clique partition in unit disk graphs (2009)
Dumitrescu, Adrian, Pach, János
The minimum clique partition (MCP) problem is that of partitioning the vertex set of a given graph into a minimum number of cliques. Given $n$ points in the plane, the corresponding unit disk graph...
On stars and Steiner stars. II (2008)
Dumitrescu, Adrian, Tóth, Csaba D., Xu, Guangwu
A {\em Steiner star} for a set $P$ of $n$ points in $\RR^d$ connects an arbitrary center point to all points of $P$, while a {\em star} connects a point $p\in P$ to the remaining $n-1$ points of $P$....
Analysis of two Sweep-line Algorithms for Constructing Spanning Trees and Steiner Trees 1 (2008)
Adrian Dumitrescu, Csaba D. Tóth
Abstract: We give a tight analysis of an old and popular sweep-line heuristic for constructing a spanning tree of a set of n points in the plane. The algorithm sweeps a vertical line across the input...
Adrian Dumitrescu, Ichiro Suzuki, Masafumi Yamashita, Adrian Dumitrescu, Masafumi Yamashita
In this paper, we examine the problem of dynamic selfreconfiguration of a modular robotic system (frequently referred to as a self-reconfigurable or metamorphic system), to a formation aimed at...
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. As a generalization of the classical...
Motion planning and reconfiguration for systems of multiple objects (2008)
This chapter surveys some recent results on motion planning and reconfiguration for systems of multiple objects and for modular systems with applications in robotics. 1
Ramsey-type results for unions of comparability graphs and convex sets in
Improved Lower Bound on the Geometric Dilation of Point Sets (2008)
Adrian Dumitrescu Ansgar, Adrian Dumitrescu, Ansgar Grüne, Günter Rote
Let G be an embedded planar graph whose edges are curves. The detour between two points p and q (on edges or vertices) of G is the length of a shortest path connecting p and q in G divided by their...
Light Orthogonal Networks with Constant Geometric Dilation ∗ (2008)
Adrian Dumitrescu, Csaba D. Tóth
An orthogonal spanner network for a given set of n points in the plane is a plane straight line graph with axis-aligned edges that connects all input points. We show that for any set of n points in...
ported by the Austrian FWF Joint Research Project ’Industrial Geometry ’ S9205-N12. (2008)
Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, ...
Abstract: This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are compatible if they have the same vertex set and their union is also non-crossing. Our first...
Light Orthogonal Networks with Constant Geometric Dilation ∗ (2008)
Adrian Dumitrescu, Csaba D. Tóth
An orthogonal spanner network for a given set of n points in the plane is a plane straight line graph with axis-aligned edges that connects all input points. We show that for any set of n points in...
Adrian Dumitrescu, Suny Stony Brook, William Steiger
We study space/time tradeo#s for querying some combinatorial structures. In the first, given an arrangement of n lines in general position in the plane, a query for a real number t asks about...
Ramsey-Type Results for Unions of Comparability Graphs and Convex Sets in Restricted Position (2007)
A graph on n vertices which is the union of two comparability graphs on the same vertex set, always contains a clique or independent set of size n 1 3 . On the other hand, there exist such graphs for...
Monotone Paths in Line Arrangements with a Small Number of Directions. Manuscript (2007)
We give subquadratic bounds on the maximum length of an x-monotone path in an arrangement of n lines with at most C log log n directions, where C is a suitable constant. For instance, the maximum...
The cost of cutting out convex n-gons (2007)
Given a convex n-gon P drawn on a piece of paper Q of unit diameter we prove that it can be cut with a total cost of O(log n). This bound is shown to be asymptotically tight: a regular n-gon (whose...
We show that any two-colored set of n points in general position in the plane can be partitioned into at most d n+1 2 e monochromatic subsets, whose convex hulls are pairwise disjoint. This bound...
Space-time trade-os for some ranking and searching queries (2007)
Adrian Dumitrescu, William Steiger
We study space/time tradeos for querying some combinatorial structures. In the rst, given an arrangement of n lines in general position in the plane, a query for a real number t asks about Rank(t),...
Matching colored points in the plane: some new results (2007)
Let S be a set with n = w+b points in general position in the plane, w of them white, and b of them black. We consider the problem of computing G(S), a largest non-crossing matching of pairs of...
empty convex quadrilaterals, less than 1:229n (2007)
A conguration of n points in general position in the plane is described which has less than
Extreme Distances in Multicolored Point Sets (2007)
Adrian Dumitrescu Yz, Adrian Dumitrescu, Sumanta Guha
Given a set of n colored points in some d-dimensional Euclidean space, a bichromatic closest (resp. farthest) pair is a closest (resp. farthest) pair of points of dierent colors. We present ecient...
Ramsey-Type Results for Unions of Comparability Graphs (2007)
Adrian Dumitrescu Computer, Adrian Dumitrescu
It is well known that the comparability graph of any partially ordered set of n elements contains either a clique or an independent set of size at least n. In this note we show that any graph of n...
On a Coloring Problem for the Integer Grid (2007)
Adrian Dumitrescu, Rados Radoicic
János Pach asked whether for any 2-coloring of the points of the integer grid in the plane, there exist arbitrary long sequences of consecutive collinear points of the same color. We answer this...
On Distinct Distances From a Vertex (2007)
Of Convex Polygon, Adrian Dumitrescu
Given a set P of n points in convex position in the plane, we prove that there exists a point p 2 P such that the number of distinct distances from p is at least d(13n 6)=36e. The best previous...
Efficient Algorithms for Generation of Combinatorial Covering Suites (2007)
In this note we describe efficient algorithms for generating tests that cover a prescribed set of combinations of a software system's input parameters. Our methods for obtaining uniform t-wise...
Extremal problems on triangle areas in two and three dimensions (2007)
Dumitrescu, Adrian, Sharir, Micha, Toth, Csaba D.
The study of extremal problems on triangle areas was initiated in a series of papers by Erd\H{o}s and Purdy in the early 1970s. In this paper we present new results on such problems, concerning the...
On the number of tetrahedra with minimum, unit, and distinct volumes in three-space (2007)
Toth, Csaba D., Dumitrescu, Adrian
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...
Compatible Geometric Matchings (2007)
Aichholzer, Oswin, Bereg, Sergey, Dumitrescu, Adrian, García, Alfredo, Huemer, Clemens, Hurtado, Ferran, ...
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...
Compatible Geometric Matchings (2007)
Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, ...
Abstract: This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are compatible if they have the same vertex set and their union is also non-crossing. Our first...
Axis-aligned traversals of points with a minimum number of turns (2007)
Sergey Bereg, Prosenjit Bose, Adrian Dumitrescu, Ferran Hurtado, Pavel Valtr
Abstract Given a finite set of points S in Rd, consider visiting the points in S with a polygonal path whichmakes a minimum number of turns, or equivalently, has the the minimum number of segments...
Distinct triangle areas in a planar point set (2007)
Adrian Dumitrescu, Csaba D. T'oth
Abstract Erd""os, Purdy, and Straus conjectured that the number of distinct (nonzero) areas of the trianglesdetermined by n noncollinear points in the plane is at least b n-12 c,...
On two representation problems with infinite multiplicity (2007)
Abstract We study two representation problems in number theory:(I) Erd""os and Sur'anyi proved that every integer n can be represented in infinitely many ways in theform k =...
On the number of tetrahedra with minimum,unit, and distinct volumes in three-space* (2007)
Adrian Dumitrescu, Csaba D. T'oth
Abstract We formulate and give partial answers to several combinatorial problems on volumes of simplicesdetermined by n points in 3-space, and in general in d dimensions. (i) The number of tetrahedra...
Distinct triangle areas in a planar point set (2007)
Adrian Dumitrescu, Csaba D. Tóth
Erdős, Purdy, and Straus conjectured that the number of distinct (nonzero) areas of the triangles determined by n noncollinear points in the plane is at least ⌊ n−1 2 ⌋, which is attained for...
Reconfigurations in graphs and grids (2006)
Gruia Călinescu, Adrian Dumitrescu, János Pach
Let G be a connected graph, and let V and V ′ two n-element subsets of its vertex set V (G). Imagine that we place a chip at each element of V and we want to move them into the positions of V ′...
Improved lower bound on the geometric dilation of point sets (2005)
Adrian Dumitrescu, Ansgar Grüne, Günter Rote
Let G be an embedded planar graph whose edges are curves. The detour between two points p and q (on edges or vertices) of G is the length of a shortest path connecting p and q in G divided by their...
On Geometric Dilation and Halving Chords (2005)
Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein, Günter Rote
Let G be an embedded planar graph whose edges may be curves. The detour between two points, p and q (on edges or vertices) of G, is the ratio between the shortest path in G between p and q and their...
On the Geometric Dilation of Closed Curves, Graphs and Point Sets (2005)
Adrian Dumitrescu, Annette Ebbers-baumann, Ansgar Grüne, Rolf Klein, Günter Rote
Let G be an embedded planar graph whose edges are curves. The detour between two points p and q (on edges or vertices) of G is the ratio between the length of a shortest path connecting p and q in G...
On the Geometric Dilation of Closed Curves, Graphs and Point Sets (2005)
Adrian Dumitrescu, Annette Ebbers-baumann
Abstract Let G be an embedded planar graph whose edges are curves. The detour between two points p and q (on edges or vertices) of G is the ratio between the length of a shortest path connecting p...
On geometric dilation and halving chords (2005)
Adrian Dumitrescu, Annette Ebbers-baumann, Ansgar Grüne, Rolf Klein, Günter Rote
Abstract. Let G be an embedded planar graph whose edges may be curves. The detour between two points, p and q (on edges or vertices) of G, is the ratio between the shortest path in G between p and q...
P.J.: Separating points by axisparallel lines (2005)
Gruia Călinescu, Adrian Dumitrescu
Peng-Jun Wan ¢ We study the problem of separating £ points in the plane, no two of which have the same ¤ or ¥-coordinate using a minimum number of vertical and horizontal lines avoiding the...
On the geometric dilation of closed curves, graphs, and point sets (2004)
Dumitrescu, Adrian, Ebbers-Baumann, Annette, Grüne, Ansgar, Klein, Rolf, Rote, Günter
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...
We study dynamic self-reconfiguration of modular metamorphic systems. We guarantee the feasibility of motion planning in a rectangular model consisting of square modules that are allowed to slide...
Generating Small Combinatorial Test Suites to Cover Input-Output Relationships (2004)
Christine T. Cheng, Adrian Dumitrescu, Patrick J. Schroeder
In this paper, we consider a problem that arises in black box testing: generating small test suites (i.e., sets of test cases) where the combinations that have to be covered are specified by...
On the geometric dilation of curves and point sets (2004)
Adrian Dumitrescu, Ansgar Grüne, Günter Rote
Let G be an embedded planar graph whose edges are curves. The detour between two points u and v (on edges or vertices) of G is the ratio between the shortest path in G between u and v and their...
An Approximation Algorithm for Cutting Out Convex Polygons (2004)
Adrian Dumitres Cu, Adrian Dumitrescu
We provide an O(log n)-approximation algorithm for the following problem. Given a convex n-gon P , drawn on a convex piece of paper, cut P out of the piece of paper in the cheapest possible way. No...
Generating small combinatorial test suites to cover input-output relationships (2003)
Christine Cheng, Adrian Dumitrescu, Patrick Schroeder
In this paper, we consider a problem that arises in black box testing: generating small test suites (i.e., sets of test cases) where the combinations that have to be covered are specified by...
Formations for Fast Locomotion of Metamorphic Robotic Systems (2003)
Adrian Dumitrescu, Ichiro Suzuki, Masafumi Yamashita
In this article we examine the problem of dynamic self-recon guration of a modular robotic system (frequently referred to as self-recon gurable or metamorphic system), to a formation aimed at...
Extreme Distances in Multicolored Point Sets (2003)
Adrian Dumitrescu, Sumanta Guha
Given a set of n coloredpointsinsomed-dimensional Euclidean space, a bichromatic closest (resp. farthest) pair is a closest (resp. farthest) pair of points of different colors. We present efficient...
Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles (2001)
Adrian Dumitrescu, Micha Sharir
We provide a variety of new results, including upper and lower bounds, as well as simpler proof techniques for the ecient construction of binary space partitions (BSP's) of axis-parallel...
Approximation algorithms for tsp with neighborhoods in the plane (2001)
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. As a generalization of the classical...
Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles (2001)
Adrian Dumitrescu, Micha Sharir
We provide a variety of new results, including upper and lower bounds, as well as simpler proof techniques for the ecient construction of binary space partitions (BSP's) of axis-parallel...
Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles (2001)
Adrian Dumitrescu, Micha Sharir
We provide a variety of new results, including upper and lower bounds, as well as simpler proof techniques for the ecient construction of binary space partitions (BSP's) of axis-parallel...
Approximation algorithms for tsp with neighborhoods in the plane (2001)
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. As a generalization of the classical...
Enumerating Triangulation Paths (2000)
Adrian Dumitrescu, Bernd Gärtner, Samuele Pedroni, Emo Welzl
Recently, Aichholzer introduced the remarkable concept of the so-called triangulation path (of a triangulation with respect to a segment), which has the potential of providing efficient counting of...
On a Matching Problem in the Plane (2000)
Adrian Dumitrescu, William Steiger
Let S be a set with n = w+ b points in general position in the plane, w of them white, and b of them black, where w and b are even numbers. We show that there exists a matching of points of the same...
Enumerating triangulation paths (2000)
Adrian Dumitrescu, Bernd Gärtner, Samuele Pedroni, Emo Welzl
Recently, Aichholzer introduced the remarkable concept of the so-called triangulation path (of a triangulation with respect to a segment), which has the potential of providing efficient counting of...
Ramsey-Type Results for Unions of Comparability Graphs (1999)
It is well known that the comparability graph of any partially ordered set of n elements contains either a clique or an independent set of size at least p n. In this note we show that any graph of n...
On Two Lower Bound Constructions (1999)
We address two problems. In the first, we refine the analysis of a lower bound construction of a point set having many non-crossing spanning trees. We also give more precise upper bounds on the...
Several problems in combinatorial geometry / (1999)
"Graduate Program in Computer Science."
Motion Planning for Metamorphic Systems: Feasibility, Decidability and Distributed Reconfiguration
Adrian Dumitrescu, Ichiro Suzuki, Masafumi Yamashita
In this article we address a number of issues related to motion planning and analysis of rectangular metamorphic robotic systems. We first present a distributed algorithm for reconfiguration that...