Search

Given a set P of m ⩾ 3 points in general position in the plane, we want to find the smallest possible number of convex polygons with vertices in P such that the edges of all these polygons contain all the m 2 straight line segments determined by the points of P. We show that if m is odd, the answer is (m 2 - 1) / 8 regardless of the choice of P. In this case there is even a partitioning of the edges of the complete geometric graph on m vertices into (m 2 - 1) / 8 convex polygons. The answer in the case where m is even depends on the choice of P and not only on m. Nearly tight lower and upper bounds follow in the case where m is even. [ABSTRACT FROM AUTHOR]

Given a finite group G acting freely on a compact metric space M, and ε > 0 , we define the G-Borsuk graph on M by drawing edges x ∼ y whenever there is a non-identity g ∈ G such that d x , g y ≤ ε . We show that when ε is small, its chromatic number is determined by the topology of M via its G-covering number, which is the minimum k such that there is a closed cover M = F 1 ∪ ⋯ ∪ F k with F i ∩ g (F i) = ∅ for all g ∈ G \ { 1 } . We are interested in bounding this number. We give lower bounds using G-actions on Hom-complexes, and upper bounds using a recursive formula on the dimension of M. We conjecture that the true chromatic number coincides with the lower bound, and give computational evidence. We also study random G-Borsuk graphs, which are random induced subgraphs. For these, we compute thresholds for ε that guarantee that the chromatic number is still that of the whole G-Borsuk graph. Our results are tight (up to a constant) when the G-index and dimension of M coincide. [ABSTRACT FROM AUTHOR]

This article deals with the complexity of problems related to finding cost‐efficient, disaster‐aware cable routes. We overview various mathematical problems studied to augment a backbone network topology to make it more robust against regional failures. These problems either consider adding a single cable, multiple cables, or even nodes too. They adapt simplistic or more sophisticated regional failure models. Their objective is to identify the network's weak points or minimize the investment cost concerning the risk of a network outage. We investigate the tradeoffs in mathematical modeling for the same real‐world scenario, where more sophisticated models face more computationally challenging problems. We have seen how efficiently computational geometry algorithms can be used to solve simplified problems even for sufficiently large networks. In this article, we aim to understand why different mathematical models formulated for the same real‐world scenario can or cannot be solved efficiently. In particular, we show simplistic mathematical models that formulate NP‐hard problems. [ABSTRACT FROM AUTHOR]

For sets of n points, n even, in general position in the plane, we consider straight-line drawings of perfect matchings on them. It is well known that such sets admit at least C n / 2 different plane perfect matchings, where C n / 2 is the n/2-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have k crossings. We show the following results. (1) For every k ≤ 1 64 n 2 - 35 32 n n + 1225 64 n , any set with n points, n sufficiently large, admits a perfect matching with exactly k crossings. (2) There exist sets of n points where every perfect matching has at most 5 72 n 2 - n 4 crossings. (3) The number of perfect matchings with at most k crossings is superexponential in n if k is superlinear in n. (4) Point sets in convex position minimize the number of perfect matchings with at most k crossings for k = 0 , 1 , 2 , and maximize the number of perfect matchings with n / 2 2 crossings and with n / 2 2 - 1 crossings. [ABSTRACT FROM AUTHOR]

Let S be a set of n points in the plane in general position. Two line segments connecting pairs of points of Scross if they have an interior point in common. Two vertex-disjoint geometric graphs with vertices in Scross if there are two edges, one from each graph, which cross. A set of vertex-disjoint geometric graphs with vertices in S is called mutually crossing if any two of them cross. We show that there exists a constant c such that from any family of n mutually-crossing triangles, one can always obtain a family of at least n c mutually-crossing 2-paths (each of which is the result of deleting an edge from one of the triangles) and provide an example that implies that c cannot be taken to be larger than 2/3. Then, for every n we determine the maximum number of crossings that a Hamiltonian cycle on a set of n points might have, and give examples achieving this bound. Next, we construct a point set whose longest perfect matching contains no crossings. We also consider edges consisting of a horizontal and a vertical line segment joining pairs of points of S, which we call elbows, and prove that in any point set S there exists a family of ⌊ n / 4 ⌋ vertex-disjoint mutually-crossing elbows. Additionally, we show a point set that admits no more than n/3 mutually-crossing elbows. Finally we study intersecting families of graphs, which are not necessarily vertex disjoint. A set of edge-disjoint graphs with vertices in S is called an intersecting family if for any two graphs in the set we can choose an edge in each of them such that they cross. We prove a conjecture by Lara and Rubio-Montiel (Acta Math Hung 15(2):301–311, 2019, ), namely, that any set S of n points in general position admits a family of intersecting triangles with a quadratic number of elements. For points in convex position we prove that any set of 3n points in convex position contains a family with at least n 2 intersecting triangles. [ABSTRACT FROM AUTHOR]

Hypergraph, as a generalization of the notions of graph and simplicial complex, has gained a lot of attention in many fields. It is a relatively new mathematical model to describe the high-dimensional structure and geometric shapes of data sets. In this paper,we introduce the neighborhood hypergraph model for graphs and combine the neighborhood hypergraph model with the persistent (embedded) homology of hypergraphs. Given a graph,we can obtain a neighborhood complex introduced by L. Lovász and a filtration of hypergraphs parameterized by aweight function on the power set of the vertex set of the graph. Theweight function can be obtained by the construction fromthe geometric structure of graphs or theweights on the vertices of the graph. We show the persistent theory of such filtrations of hypergraphs. One typical application of the persistent neighborhood hypergraph is to distinguish the planar square structure of cisplatin and transplatin. Another application of persistent neighborhood hypergraph is to describe the structure of small fullerenes such as C20. The bond length and the number of adjacent carbon atoms of a carbon atom can be derived from the persistence diagram. Moreover, our method gives a highly matched stability prediction (with a correlation coefficient 0.9976) of small fullerene molecules.

A geometric graph is a graph drawn in the plane so that its vertices and edges are represented by points in general position and straight line segments, respectively. A vertex of a geometric graph is called pointed if it lies outside of the convex hull of its neighbours. We show that for a geometric graph with n vertices and e edges there are at least n 2 2 e / n 3 pairs of disjoint edges provided that 2 e ≥ n and all the vertices of the graph are pointed. Besides, we prove that if any edge of a geometric graph with n vertices is disjoint from at most m edges, then the number of edges of this graph does not exceed n (1 + 8 m + 3) / 4 provided that n is sufficiently large. These two results are tight for an infinite family of graphs. [ABSTRACT FROM AUTHOR]

A geometric graph is a graph whose vertex set is a set of points in general position in the plane, and its edges are straight line segments joining these points. We show that for every integer k ≥ 2 , there exists a constant c > 0 such that the following holds. The edges of every dense geometric graph, with sufficiently many vertices, can be colored with k colors, such that the number of pairs of edges of the same color that cross is at most (1 / k − c) times the total number of pairs of edges that cross. The case when k = 2 and G is a complete geometric graph, was proved by Aichholzer et al. (2019) [2]. [ABSTRACT FROM AUTHOR]

We use production matrices to count several classes of geometric graphs. We present novel production matrices for non-crossing partitions, connected geometric graphs, and k -angulations, which provide another, simple and elegant, way of counting the number of such objects. Counting geometric graphs is then equivalent to calculating the powers of a production matrix. Applying the technique of Riordan Arrays to these production matrices, we establish new formulas for the numbers of geometric graphs as well as combinatorial identities derived from the production matrices. Further, we obtain the characteristic polynomial and the eigenvectors of such production matrices. [ABSTRACT FROM AUTHOR]

A geometric graph is a combinatorial graph, endowed with a geometry that is inherited from its embedding in a Euclidean space. Formulation of a meaningful measure of (dis-)similarity in both the combinatorial and geometric structures of two such geometric graphs is a challenging problem in pattern recognition. We study two notions of distance measures for geometric graphs, called the geometric edit distance (GED) and geometric graph distance (GGD). While the former is based on the idea of editing one graph to transform it into the other graph, the latter is inspired by inexact matching of the graphs. For decades, both notions have been lending themselves well as measures of similarity between attributed graphs. If used without any modification, however, they fail to provide a meaningful distance measure for geometric graphs—even cease to be a metric. We have curated their associated cost functions for the context of geometric graphs. Alongside studying the metric properties of GED and GGD, we investigate how the two notions compare. We further our understanding of the computational aspects of GGD by showing that the distance is NP -hard to compute, even if the graphs are planar and arbitrary cost coefficients are allowed. As a computationally tractable alternative, we propose in this paper the Graph Mover's Distance (GMD), which has been formulated as an instance of the earth mover's distance. The computation of the GMD between two geometric graphs with at most n vertices takes only O (n 3) -time. The GMD demonstrates extremely promising empirical evidence at recognizing letter drawings. [ABSTRACT FROM AUTHOR]

This study presents a generalised critical infrastructures resilience model for extreme events with a focus on power grids. Infrastructures are modelled as three domains – physical, cyber, and human. Each domain is described with respect to the services it provides. Each domain is represented by geometric graphs for each service it provides. The resilience models use geometric graphs with each graph's nodes and edges characterised based on relevant attributes. This study also discusses various applied aspects related to resilience models including the impact of changing operating environment, human-driven processes, such as logistics, and service buffers. Due to their stated particular importance in the U.S. Presidential Policy Directive 21, particular attention is placed on the power infrastructure and its impact on the public communication infrastructures as a main critical load. This study focuses on the multi-time scale power system operation to capture cascading outages within, and subsequently to its dependent infrastructure – the public communication system (e.g. wireless or ‘cellular’ communication networks) as a main critical load. This study illustrates the merits of the proposed models in calculating resilience in extreme events and derives physical domain representation for electric and communication systems using cell tower and substation data from the USA.

A graph G is a homomorphic preimage of another graph H, or equivalently G is H-colorable, if there exists a graph homomorphism f : G → H. A geometric graph Ḡ is a simple graph G together with a straight line drawing of G in the plane with the vertices in general position. A geometric homomorphism (respectively, isomorphism) Ḡ → H̄ is a graph homomorphism (respectively, isomorphism) that preserves edge crossings (respectively, and non-crossings). The homomorphism poset ℊ of a graph G is the set of isomorphism classes of geometric realizations of G partially ordered by the existence of injective geometric homomorphisms. A geometric graph Ḡ is ℋ-colorable if Ḡ → H̄ for some H̄ ∈ ℋ. In this paper, we provide necessary and sufficient conditions for Ḡ to be 𝒫n-colorable for n ≥ 2. Along the way, we also provide necessary and sufficient conditions for Ḡ to be 𝒦2,3-colorable.

In 2002, Even et al. introduced and studied the notion of conflict-free colorings of geometrically defined hypergraphs. They motivated it by frequency assignment problems in cellular networks. This notion has been extensively studied since then. A conflict-free coloring of a graph is a coloring of its vertices such that the neighborhood (pointed or closed) of each vertex contains a vertex whose color differs from the colors of all other vertices in that neighborhood. In this paper we study conflict-free colorings of intersection graphs of geometric objects. We show that any intersection graph of n pseudo-discs in the plane admits a conflict-free coloring with O (log n) colors, with respect to both closed and pointed neighborhoods. We also show that the latter bound is asymptotically sharp. Using our methods, we obtain the following strengthening of the two main results of Even et al.: Any family F of n discs in the plane can be colored with O (log n) colors in such a way that for any disc B in the plane, not necessarily from F , the set of discs in F that intersect B contains a uniquely-colored element. In view of the original motivation to study such colorings, this strengthening suggests further applications to frequency assignment in wireless networks. Finally, we present bounds on the number of colors needed for conflict-free colorings of other classes of intersection graphs, including intersection graphs of axis-parallel rectangles and of ρ -fat objects in the plane. [ABSTRACT FROM AUTHOR]

A set P = H ∪ { w } of n + 1 points in general position in the plane is called a wheel set if all points but w are extreme. We show that for the purpose of counting crossing-free geometric graphs on such a set P, it suffices to know the frequency vector of P. While there are roughly 2 n distinct order types that correspond to wheel sets, the number of frequency vectors is only about 2 n / 2 . We give simple formulas in terms of the frequency vector for the number of crossing-free spanning cycles, matchings, triangulations, and many more. Based on that, the corresponding numbers of graphs can be computed efficiently. In particular, we rediscover an already known formula for w-embracing triangles spanned by H. Also in higher dimensions, wheel sets turn out to be a suitable model to approach the problem of computing the simplicial depth of a point w in a set H, i.e., the number of w-embracing simplices. While our previous arguments in the plane do not generalize easily, we show how to use similar ideas in R d for any fixed d. The result is an O (n d - 1) time algorithm for computing the simplicial depth of a point w in a set H of n points, improving on the previously best bound of O (n d log n) . Based on our result about simplicial depth, we can compute the number of facets of the convex hull of n = d + k points in general position in R d in time O (n max { ω , k - 2 }) where ω ≈ 2.373 , even though the asymptotic number of facets may be as large as n k . [ABSTRACT FROM AUTHOR]

Suppose V⊂R2, |V|=2m. A set M={I1,...,Im} of m line segments is a matching of V if V is the set of endpoints of I1,...,Im. The length of M is the sum of lengths of I1,...,Im. M is called a crossing matching if every two segments Iμ,Iν cross. It is shown that a crossing matching M (if it exists) is longer than any other matching of V. In fact, if {I1,...,Im} is a crossing matching of V, and (a1,b1),(a2,b2),...,(am,bm) is an arbitrary matching of V, then, within the union ⋃j=1mIj, we can find m polygonal paths that connect aν to bν (ν=1,...,m) and are pairwise almost disjoint. In the same vein: suppose |V|=2m+1≥5. A Hamiltonian (2m+1)‐circuit A on V is an asterisk if every two nonadjacent edges of A cross. It is shown that if V admits an asterisk A, then A is longer than any other 2‐regular geometric graph on V. This proves an old conjecture by the first author. [ABSTRACT FROM AUTHOR]

In this paper, we study resolvability and fault-tolerant resolvability of convex polytopes and related geometric graphs. Imran et al. (2010) [18] raised an open problem asserting that whether or not every family of convex polytope has a constant metric dimension. Raza et al. (2018) [28] studied the fault-tolerant metric dimension of certain families of convex polytopes. They also concluded their study with an open problem asking whether or not every family of convex polytope has a constant fault-tolerant metric dimension. In this paper, we provide negative answers to both of the aforementioned open problems. We answer the first question by constructing a family of convex polytopes with an unbounded metric dimension. By proving a result between resolvability and fault-tolerant resolvability structures of a graph, we show that the family of convex polytope with an unbounded metric dimension also possesses an unbounded fault-tolerant resolvability structure. Moreover, we construct three more infinite families of graphs which are closely related to convex polytopes, having an unbounded metric dimension. [ABSTRACT FROM AUTHOR]

Finding a maximal independent set (MIS) in a graph is one of the fundamental problems in distributed computing. Researchers in this community are trying to close the time complexity gap of computing a MIS in a graph, way back from Luby's [STOC'85] O (log n) time (randomized) algorithm and Linial's [SICOMP'92] Ω (log ∗ n) lower bound result (n is the number of nodes of the graph). Since then, an extensive research has been done on this problem, however, most of the results are randomized and we are lack of efficient deterministic solution. In fact, no polylogarithmic (in n) time deterministic algorithm is known so far in general graphs — an open question raised by Linial in 1993 [Comb. Probab. Comput.'93]. In this paper, we study the MIS problem in geometric graphs, a class of graphs which has both theoretical and practical importance. We present O (1) -time deterministic algorithms (hence, optimal) for computing MIS in unit interval graphs, unit square graphs and unit disk graphs. The same idea applies to develop optimal MIS algorithm for higher dimensional unit balls and unit hypercubes. We further extend the MIS algorithms to compute approximate maximum independent set (MaxIS) in the above geometric graph classes. The theoretical results are corroborated through extensive experiments to show the effectiveness and efficiency of our algorithms. Our algorithms are fully decentralized, scalable, and robust. In general, nodes exchange only O (log n) bits message through an edge per communication. Moreover, being local, our algorithms are also suitable in failure model, self-stabilizing and appropriate for dynamic environment. • We study the Maximal and Maximal Independent Sets in geometric graphs in distributed computing model. • Our algorithms work in the CONGEST model of distributed computation. • We design constant time (optimal) distributed algorithms in unit interval, square, disk, and higher dimensional graphs. • We perform comprehensive experimental evaluation and highlight the efficiency of the algorithms. • Experimental results guarantee that our algorithms perform better than the theoretical proven bound. [ABSTRACT FROM AUTHOR]

Given a set of points in the plane, we want to establish a connected spanning graph between these points, called connection network, that consists of several disjoint layers. Motivated by sensor networks, our goal is that each layer is connected, spanning, and plane. No edge in this connection network is too long in comparison to the length needed to obtain a spanning tree. We consider two different approaches. First we show an almost optimal centralized approach to extract two layers. Then we consider a distributed model in which each point can compute its adjacencies using only information about vertices at most a predefined distance away. We show a constant factor approximation with respect to the length of the longest edge in the graphs. In both cases the obtained layers are plane. [ABSTRACT FROM AUTHOR]

Gromov hyperbolicity is an interesting geometric property, and so it is natural to study it in the context of geometric graphs. It measures the tree-likeness of a graph from a metric viewpoint. In particular, we are interested in circular-arc graphs, which is an important class of geometric intersection graphs. In this paper we give sharp bounds for the hyperbolicity constant of (finite and infinite) circular-arc graphs. Moreover, we obtain bounds for the hyperbolicity constant of the complement and line of any circular-arc graph. In order to do that, we obtain new results about regular, chordal and line graphs which are interesting by themselves. [ABSTRACT FROM AUTHOR]

We present improved upper bounds on the spanning ratio of constrained 𝜃 -graphs with at least 6 cones and constrained Yao-graphs with 5 or at least 7 cones. Given a set of points in the plane, a Yao-graph partitions the plane around each vertex into m disjoint cones, each having aperture 𝜃 = 2 π / m , and adds an edge to the closest vertex in each cone. Constrained Yao-graphs have the additional property that no edge properly intersects any of the given line segment constraints. Constrained 𝜃 -graphs are similar to constrained Yao-graphs, but use a different method to determine the closest vertex. We present tight bounds on the spanning ratio of a large family of constrained 𝜃 -graphs. We show that constrained 𝜃 -graphs with 4 k + 2 (k ≥ 1 and integer) cones have a tight spanning ratio of 1 + 2 sin (𝜃 / 2) , where 𝜃 is 2 π / (4 k + 2). We also present improved upper bounds on the spanning ratio of the other families of constrained 𝜃 -graphs. These bounds match the current upper bounds in the unconstrained setting. We also show that constrained Yao-graphs with an even number of cones (m ≥ 8) have spanning ratio at most 1 / (1 − 2 sin (𝜃 / 2)) and constrained Yao-graphs with an odd number of cones (m ≥ 5) have spanning ratio at most 1 / (1 − 2 sin (3 𝜃 / 8)). As is the case with constrained 𝜃 -graphs, these bounds match the current upper bounds in the unconstrained setting, which implies that like in the unconstrained setting using more cones can make the spanning ratio worse. [ABSTRACT FROM AUTHOR]

Highlights • Novel approach for processing Projective Mapping data, using geometric 2D techniques. • Validated by four tasting sessions with three types of panels tasting different wines. • Similar positioning of samples as the state-of-the-art technique MFA. • Further information, about connections between samples, for pairs of samples at similar distance. • Computationally more efficient than MFA, thus able to manage a significantly larger number of assessors. Abstract This paper introduces SensoGraph, a novel approach for fast sensory evaluation using two-dimensional geometric techniques. In the tasting sessions, the assessors follow their own criteria to place samples on a tablecloth, according to the similarity between samples. In order to analyse the data collected, first a geometric clustering is performed to each tablecloth, extracting connections between the samples. Then, these connections are used to construct a global similarity matrix. Finally, a graph drawing algorithm is used to obtain a 2D consensus graphic, which reflects the global opinion of the panel by (1) positioning closer those samples that have been globally perceived as similar and (2) showing the strength of the connections between samples. The proposal is validated by performing four tasting sessions, with three types of panels tasting different wines, and by developing a new software to implement the proposed techniques. The results obtained show that the graphics provide similar positionings of the samples as the consensus maps obtained by multiple factor analysis (MFA), further providing extra information about connections between samples, not present in any previous method. The main conclusion is that the use of geometric techniques provides information complementary to MFA, and of a different type. Finally, the method proposed is computationally able to manage a significantly larger number of assessors than MFA, which can be useful for the comparison of pictures by a huge number of consumers, via the Internet. [ABSTRACT FROM AUTHOR]

We consider the problem of augmenting an n -vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in O (n log 3 n) time, and (ii) the input graph is a tree, running in O (n 2 log n) time. We also present an algorithm for paths that computes a (1 + 𝜀) -approximation in O (n + 1 / 𝜀 3) time. [ABSTRACT FROM AUTHOR]

Abstract A circulant graph G is a graph on n vertices that can be numbered from 0 to n − 1 in such a way that, if two vertices x and (x + d) mod n are adjacent, then every two vertices z and (z + d) mod n are adjacent. We call layout of the circulant graph any numbering that witness this definition. A random circulant graph results from deleting each edge of G uniformly with probability 1 − p. We address the problem of finding the layout of a random circulant graph. We provide a polynomial time algorithm that approximates the solution and we bound the error of the approximation with high probability. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of designing robust algorithms for computing the minimum spanning tree, the nearest neighbor graph, and the relative neighborhood graph of a set of points in the plane, under the Euclidean metric. We use the term "robust" to denote an algorithm that can properly handle degenerate configurations of the input (such as co-circularities and collinearities) and that is not affected by errors in the flow of control due to round-off approximations. Existing asymptotically optimal algorithms that compute such graphs are either suboptimal in terms of the arithmetic precision required for the implementation, or cannot handle degeneracies, or are based on complex data structures. We present a unified approach to the robust computation of the above graphs. The approach is a variant of the general region approach for the computation of proximity graphs based on Yao graphs, first introduced in Ref. 43 (A. C.-C. Yao, On constructing minimum spanning trees in k -dimensional spaces and related problems, SIAM J. Comput.11(4) (1982) 721–736). We show that a sparse supergraph of these geometric graphs can be computed in asymptotically optimal time and space, and requiring only double precision arithmetic, which is proved to be optimal. The arithmetic complexity of the approach is measured by using the notion of degree, introduced in Ref. 31 (G. Liotta, F. P. Preparata and R. Tamassia, Robust proximity queries: An illustration of degree-driven algorithm design, SIAM J. Comput.28(3) (1998) 864–889) and Ref. 3 (J. D. Boissonnat and F. P. Preparata, Robust plane sweep for intersecting segments, SIAM J. Comput.29(5) (2000) 1401–1421). As a side effect of our results, we solve a question left open by Katajainen27 (J. Katajainen, The region approach for computing relative neighborhood graphs in the L p metric, Computing40 (1987) 147–161) about the existence of a subquadratic algorithm, based on the region approach, that computes the relative neighborhood graph of a set of points S in the plane under the L 2 metric. [ABSTRACT FROM AUTHOR]

Let P be a set of n ≥ 5 points in convex position in the plane. The path graph G ( P ) of P is an abstract graph whose vertices are non-crossing spanning paths of P , such that two paths are adjacent if one can be obtained from the other by deleting an edge and adding another edge. We prove that the automorphism group of G ( P ) is isomorphic to D n , the dihedral group of order 2 n . The heart of the proof is an algorithm that first identifies the vertices of G ( P ) that correspond to boundary paths of P , where the identification is unique up to an automorphism of K ( P ) as a geometric graph, and then identifies (uniquely) all edges of each path represented by a vertex of G ( P ) . The complexity of the algorithm is O ( N log ⁡ N ) where N is the number of vertices of G ( P ) . [ABSTRACT FROM AUTHOR]

The maximum number of non-crossing straight-line perfect matchings that a set of n points in the plane can have is known to be O ( 10.0438 n ) and Ω ⁎ ( 3 n ) . The lower bound, due to García, Noy, and Tejel (2000), is attained by the double chain , which has Θ ( 3 n / n Θ ( 1 ) ) such matchings. We reprove this bound in a simplified way that uses the novel notion of down-free matchings . We then apply this approach to several other constructions. As a result, we improve the lower bound. First we show that the double zigzag chain with n points has Θ ⁎ ( λ n ) non-crossing perfect matchings with λ ≈ 3.0532 . Next we analyze further generalizations of double zigzag chains – double r-chains . The best choice of parameters leads to a construction that has Θ ⁎ ( ν n ) matchings with ν ≈ 3.0930 . The derivation of this bound requires an analysis of a coupled dynamic-programming recursion between two infinite vectors. [ABSTRACT FROM AUTHOR]

Let P be a set of n points in general position in the plane. Given a convex geometric shape S , a geometric graph G S ( P ) on P is defined to have an edge between two points if and only if there exists a homothet of S having the two points on its boundary and whose interior is empty of points of P . A matching in G S ( P ) is said to be strong , if the homothets of S representing the edges of the matching are pairwise disjoint, i.e., they do not share any point in the plane. We consider the problem of computing a strong matching in G S ( P ) , where S is a diametral disk, an equilateral triangle, or a square. We present an algorithm that computes a strong matching in G S ( P ) ; if S is a diametral-disk, then it computes a strong matching of size at least ⌈ n − 1 17 ⌉ , and if S is an equilateral-triangle, then it computes a strong matching of size at least ⌈ n − 1 9 ⌉ . If S can be a downward or an upward equilateral-triangle, we compute a strong matching of size at least ⌈ n − 1 4 ⌉ in G S ( P ) . When S is an axis-aligned square, we compute a strong matching of size at least ⌈ n − 1 4 ⌉ in G S ( P ) , that improves the previous lower bound of ⌈ n 5 ⌉ . [ABSTRACT FROM AUTHOR]