BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let R and B be two disjoint point sets in the plane with ∣R∣=∣B∣=n. Let M={(ri,bi),i=1,2,…,n} be a perfect matching that matches points of R with points of B and maximizes ∑i=1n∥ri−bi∥, the total Euclidean distance of the matched pairs. In this paper, we prove that there exists a point o of the plane (the center of M) such that ∥ri−o∥+∥bi−o∥≤2 ∥ri−bi∥ for all i∈{1,2,…,n}.
Let P be a set of n points in R3 in general position, and let RCH(P) be the rectilinear convex hull of P. In this paper we obtain an optimal O(nlogn)-time and O(n)-space algorithm to compute RCH(P). We also obtain an efficient O(nlog2n)-time and O(nlogn)-space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of P as we rotate R3 around the z-axis. Finally we study some properties of the rectilinear convex hulls of point sets in R3.
An edge-ordered graph is a graph with a total ordering of its edges. A path P=v1v2…vk in an edge-ordered graph is called increasing if (vivi+1)>(vi+1vi+2) for all i=1,…,k−2; it is called decreasing if (vivi+1)<(vi+1vi+2) for all i=1,…,k−2. We say that P is monotone if it is increasing or decreasing. A rooted tree T in an edge-ordered graph is called monotone if either every path from the root of to a leaf is increasing or every path from the root to a leaf is decreasing. Let G be a graph. In a straight-line drawing D of G, its vertices are drawn as different points in the plane and its edges are straight line segments. Let α(G) be the maximum integer such that every edge-ordered straight-line drawing of G %under any edge labeling contains a monotone non-crossing path of length α(G). Let τ(G) be the maximum integer such that every edge-ordered straight-line drawing of G %under any edge labeling contains a monotone non-crossing complete binary tree of size τ(G). In this paper we show that α(Kn)=Ω(loglogn), α(Kn)=O(logn), τ(Kn)=Ω(logloglogn) and τ(Kn)=O(nlogn).
In 2001, Károlyi, Pach and Tóth introduced a family of point sets to solve an Erdős-Szekeres type problem; which have been used to solve several other Edős-Szekeres type problems. In this paper we refer to these sets as nested almost convex sets. A nested almost convex set X has the property that the interior of every triangle determined by three points in the same convex layer of X, contains exactly one point of X. In this paper, we introduce a characterization of nested almost convex sets. Our characterization implies that there exists at most one (up to order type) nested almost convex set of n points. We use our characterization to obtain a linear time algorithm to construct nested almost convex sets of n points, with integer coordinates of absolute values at most O(nlog25). Finally, we use our characterization to obtain an O(nlogn)-time algorithm to determine whether a set of points is a nested almost convex set.
Given two point sets R and B in the plane, with cardinalities m and n, respectively, and each set stored in a separate R-tree, we present an algorithm to decide whether R and B are linearly separable. Our algorithm exploits the structure of the R-trees, loading into the main memory only relevant data, and runs in O(mlogm+nlogn) time in the worst case. As experimental results, we implement the proposed algorithm and executed it on several real and synthetic point sets, showing that the percentage of nodes of the R-trees that are accessed and the memory usage are low in these cases. We also present an algorithm to compute the convex hull of n planar points given in an R-tree, running in O(nlogn) time in the worst case.
Given a convex polygon of n sides, one can draw n disks (called side disks) where each disk has a different side of the polygon as diameter and the midpoint of the side as its center. The intersection graph of such disks is the undirected graph with vertices the n disks and two disks are adjacent if and only if they have a point in common. We prove that for every convex polygon this graph is planar. Particularly, for n=5, this shows that for any convex pentagon there are two disks among the five side disks that do not intersect, which means that K5 is never the intersection graph of such five disks. For n=6, we then have that for any convex hexagon the intersection graph of the side disks does not contain K3,3 as subgraph.
The KLEE'S MESURE of n axis-parallel boxes in Rd is the volume of their union. It can be computed in time within O(nd/2) in the worst case. We describe three techniques to boost its computation: one based on some type of "degeneracy'' of the input, and two ones on the inherent "easiness'' of the structure of the input. The first technique benefits from instances where the MAXIMA of the input is of small size h, and yields a solution running in time within O(nlog2d−2h+hd/2)⊆O(nd/2). The second technique takes advantage of instances where no d-dimensional axis-aligned hyperplane intersects more than k boxes in some dimension, and yields a solution running in time within O(nlogn+nk(d−2)/2)⊆O(nd/2). The third technique takes advantage of instances where the \emph{intersection graph} of the input has small treewidth ω. It yields an algorithm running in time within O(n4ωlogω+n(ωlogω)d/2) in general, and in time within O(nlogn+nωd/2) if an optimal tree decomposition of the intersection graph is given. We show how to combine these techniques in an algorithm which takes advantage of all three configurations.
The Swap-Insert Correction distance from a string S of length n to another string L of length m≥n on the alphabet [1..d] is the minimum number of insertions, and swaps of pairs of adjacent symbols, converting S into L. Contrarily to other correction distances, computing it is NP-Hard in the size d of the alphabet. We describe an algorithm computing this distance in time within O(d2nmgd−1), where there are nα occurrences of α in S, mα occurrences of α in L, and where g=maxα∈[1..d]min{nα,mα−nα} measures the difficulty of the instance. The difficulty g is bounded by above by various terms, such as the length of the shortest string S, and by the maximum number of occurrences of a single character in S. Those results illustrate how, in many cases, the correction distance between two strings can be easier to compute than in the worst case scenario.
Given a set P of n points in the plane, we study the computation of the probability distribution function of both the area and perimeter of the convex hull of a random subset S of P. The random subset S is formed by drawing each point p of P independently with a given rational probability πp. For both measures of the convex hull, we show that it is \#P-hard to compute the probability that the measure is at least a given bound w. For ε∈(0,1), we provide an algorithm that runs in O(n6/ε) time and returns a value that is between the probability that the area is at least w, and the probability that the area is at least (1−ε)w. For the perimeter, we show a similar algorithm running in O(n6/ε) time. Finally, given ε,δ∈(0,1) and for any measure, we show an O(nlogn+(n/ε2)log(1/δ))-time Monte Carlo algorithm that returns a value that, with probability of success at least 1−δ, differs at most ε from the probability that the measure is at least w.
A set of intervals is independent when the intervals are pairwise disjoint. In the interval selection problem we are given a set I of intervals and we want to find an independent subset of intervals of largest cardinality. Let α(I) denote the cardinality of an optimal solution. We discuss the estimation of α(I) in the streaming model, where we only have one-time, sequential access to the input intervals, the endpoints of the intervals lie in {1,...,n}, and the amount of the memory is constrained. For intervals of different sizes, we provide an algorithm in the data stream model that computes an estimate α^ of α(I) that, with probability at least 2/3, satisfies 21(1−ε)α(I)≤α^≤α(I). For same-length intervals, we provide another algorithm in the data stream model that computes an estimate α^ of α(I) that, with probability at least 2/3, satisfies 32(1−ε)α(I)≤α^≤α(I). The space used by our algorithms is bounded by a polynomial in ε−1 and logn. We also show that no better estimations can be achieved using o(n) bits of storage. We also develop new, approximate solutions to the interval selection problem, where we want to report a feasible solution, that use O(α(I)) space. Our algorithms for the interval selection problem match the optimal results by Emek, Halld{ó}rsson and Ros{é}n [Space-Constrained Interval Selection, ICALP 2012], but are much simpler.
Finding a maximum independent set (MIS) of a given fam- ily of axis-parallel rectangles is a basic problem in computational geom- etry and combinatorics. This problem has attracted significant atten- tion since the sixties, when Wegner conjectured that the corresponding duality gap, i.e., the maximum possible ratio between the maximum independent set and the minimum hitting set (MHS), is bounded by a universal constant. An interesting special case, that may prove use- ful to tackling the general problem, is the diagonal-intersecting case, in which the given family of rectangles is intersected by a diagonal. Indeed, Chepoi and Felsner recently gave a factor 6 approximation algorithm for MHS in this setting, and showed that the duality gap is between 3/2 and 6. In this paper we improve upon these results. First we show that MIS in diagonal-intersecting families is NP-complete, providing one smallest subclass for which MIS is provably hard. Then, we derive an O(n2)-time algorithm for the maximum weight independent set when, in addition the rectangles intersect below the diagonal. This improves and extends a classic result of Lubiw, and amounts to obtain a 2-approximation algo- rithm for the maximum weight independent set of rectangles intersecting a diagonal. Finally, we prove that for diagonal-intersecting families the duality gap is between 2 and 4. The upper bound, which implies an approximation algorithm of the same factor, follows from a simple com- binatorial argument, while the lower bound represents the best known lower bound on the duality gap, even in the general case.
We consider a natural variation of the concept of stabbing a segment by a simple polygon: a segment is stabbed by a simple polygon P if at least one of its two endpoints is contained in P. A segment set S is stabbed by P if every segment of S is stabbed by P. We show that if S is a set of pairwise disjoint segments, the problem of computing the minimum perimeter polygon stabbing S can be solved in polynomial time. We also prove that for general segments the problem is NP-hard. Further, an adaptation of our polynomial-time algorithm solves an open problem posed by Löffler and van Kreveld [Algorithmica 56(2), 236--269 (2010)] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments.
In 1926, Jarník introduced the problem of drawing a convex n-gon with vertices having integer coordinates. He constructed such a drawing in the grid [1,c⋅n3/2]2 for some constant c>0, and showed that this grid size is optimal up to a constant factor. We consider the analogous problem for drawing the double circle, and prove that it can be done within the same grid size. Moreover, we give an O(n)-time algorithm to construct such a point set.
In this paper we study a facility location problem in the plane in which a single point (facility) and a rapid transit line (highway) are simultaneously located in order to minimize the total travel time from the clients to the facility, using the L1 or Manhattan metric. The rapid transit line is given by a segment with any length and orientation, and is an alternative transportation line that can be used by the clients to reduce their travel time to the facility. We study the variant of the problem in which clients can enter and exit the highway at any point. We provide an O(n3)-time algorithm that solves this variant, where n is the number of clients. We also present a detailed characterization of the solutions, which depends on the speed given in the highway.
Given a set S of n points in the plane, a \emph{radial ordering} of S with respect to a point p (not in S) is a clockwise circular ordering of the elements in S by angle around p. If S is two-colored, a \emph{colored radial ordering} is a radial ordering of S in which only the colors of the points are considered. In this paper, we obtain bounds on the number of distinct non-colored and colored radial orderings of S. We assume a strong general position on S, not three points are collinear and not three lines---each passing through a pair of points in S---intersect in a point of R2∖S. In the colored case, S is a set of 2n points partitioned into n red and n blue points, and n is even. We prove that: the number of distinct radial orderings of S is at most O(n4) and at least Ω(n3); the number of colored radial orderings of S is at most O(n4) and at least Ω(n); there exist sets of points with Θ(n4) colored radial orderings and sets of points with only O(n2) colored radial orderings.
We study a variation of the 1-center problem in which, in addition to a single supply facility, we are allowed to locate a highway. This highway increases the transportation speed between any demand point and the facility. That is, given a set S of points and v>1, we are interested in locating the facility point f and the highway h that minimize the expression maxp∈Sdh(p,f), where dh is the time needed to travel between p and f. We consider two types of highways ({\em freeways} and {\em turnpikes}) and study the cases in which the highway's length is fixed by the user (or can be modified to further decrease the transportation time).
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.