اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn Compatible Matchings
263
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A matching is compatible to two or more labeled point sets of size $n$ with labels ${1,dots,n}$ if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of $n$ points there exists a compatible matching with $lfloor sqrt {2n}rfloor$ edges. More generally, for any $ell$ labeled point sets we construct compatible matchings of size $Omega(n^{1/ell})$. As a corresponding upper bound, we use probabilistic arguments to show that for any $ell$ given sets of $n$ points there exists a labeling of each set such that the largest compatible matching has ${mathcal{O}}(n^{2/({ell}+1)})$ edges. Finally, we show that $Theta(log n)$ copies of any set of $n$ points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.
قيم البحث
اقرأ أيضاً
The Frechet distance is a metric to compare two curves, which is based on monotonous matchings between these curves. We call a matching that results in the Frechet distance a Frechet matching. There are often many different Frechet matchings and not
all of these capture the similarity between the curves well. We propose to restrict the set of Frechet matchings to natural matchings and to this end introduce locally correct Frechet matchings. We prove that at least one such matching exists for two polygonal curves and give an O(N^3 log N) algorithm to compute it, where N is the total number of edges in both curves. We also present an O(N^2) algorithm to compute a locally correct discrete Frechet matching.
An origami extrusion is a folding of a 3D object in the middle of a flat piece of paper, using 3D gadgets which create faces with solid angles. Our main concern is to make origami extrusions of polyhedrons using 3D gadgets with simple outgoing pleats
, where a simple pleat is a pair of a mountain fold and a valley fold which are parallel to each other. In this paper we present a new type of 3D gadgets with simple outgoing pleats in origami extrusions and their construction. Our 3D gadgets are downward compatible with the conventional pyramid-supported gadgets developed by Calros Natan as a generalization of the cube gadget, in the sense that in many cases we can replace the conventional gadgets with the new ones with the same outgoing pleats while the converse is not always possible. We can also change angles of the outgoing pleats under certain conditions. Unlike the conventional pyramid-supported 3D gadgets, the new ones have flat back sides above the ambient paper, and thus we can make flat-foldable origami extrusions. Furthermore, since our new 3D gadgets are less interfering with adjacent gadgets than the conventional ones, we can use wider pleats at one time to make the extrusion higher. For example, we prove that the maximal height of the prism of any convex polygon (resp. any triangle) that can be extruded with our new gadgets is more than 4/3 times (resp. $sqrt{2}$ times) of that with the conventional ones. We also present explicit constructions of division/repetition and negati
An origami extrusion is a folding of a 3D object in the middle of a flat piece of paper, using 3D gadgets which create faces with solid angles. In this paper we focus on 3D gadgets which create a top face parallel to the ambient paper and two side fa
ces sharing a ridge, with two outgoing simple pleats, where a simple pleat is a pair of a mountain fold and a valley fold. There are two such types of 3D gadgets. One is the conventional type of 3D gadgets with a triangular pyramid supporting the two side faces from inside. The other is the newer type of 3D gadgets presented in our previous paper, which improve the conventional ones in several respects: They have flat back sides above the ambient paper and no gap between the side faces; they are less interfering with adjacent gadgets so that we can make the extrusion higher at one time; they are downward compatible with conventional ones if constructible; they have a modified flat-back gadget used for repetition which does not interfere with adjacent gadgets; the angles of their outgoing pleats can be changed under certain conditions. However, there are cases where we can apply the conventional gadgets while we cannot our previous ones. The purpose of this paper is to improve our previous 3D gadgets to be completely downward compatible with the conventional ones, in the sense that any conventional gadget can be replaced by our improved one with the same outgoing pleats, but the converse is not always possible. To be more precise, we prove that for any given conventional 3D gadget there are an infinite number of improved 3D gadgets which are compatible with it, and the conventional 3D gadget can be replaced with any of these 3D gadgets without affecting any other conventional 3D gadget. Also, we see that our improved 3D gadget keep all of the above advantages over the conventional ones.
A graph $G$ whose edges are coloured (not necessarily properly) contains a full rainbow matching if there is a matching $M$ that contains exactly one edge of each colour. We refute several conjectures on matchings in hypergraphs and full rainbow matc
hings in graphs, made by Aharoni and Berger and others.
We study the computational complexity of several problems connected with finding a maximal distance-$k$ matching of minimum cardinality or minimum weight in a given graph. We introduce the class of $k$-equimatchable graphs which is an edge analogue o
f $k$-equipackable graphs. We prove that the recognition of $k$-equimatchable graphs is co-NP-complete for any fixed $k ge 2$. We provide a simple characterization for the class of strongly chordal graphs with equal $k$-packing and $k$-domination numbers. We also prove that for any fixed integer $ell ge 1$ the problem of finding a minimum weight maximal distance-$2ell$ matching and the problem of finding a minimum weight $(2 ell - 1)$-independent dominating set cannot be approximated in polynomial time in chordal graphs within a factor of $delta ln |V(G)|$ unless $mathrm{P} = mathrm{NP}$, where $delta$ is a fixed constant (thereby improving the NP-hardness result of Chang for the independent domination case). Finally, we show the NP-hardness of the minimum maximal induced matching and independent dominating set problems in large-girth planar graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
