اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNon Total-Unimodularity Neutralized Simplicial Complexes
136
0
0.0
(
0
)
نشر من قبل
Bala Krishnamoorthy
تاريخ النشر
2013
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Given a simplicial complex K with weights on its simplices and a chain on it, the Optimal Homologous Chain Problem (OHCP) is to find a chain with minimal weight that is homologous (over the integers) to the given chain. The OHCP is NP-complete, but if the boundary matrix of K is totally unimodular (TU), it becomes solvable in polynomial time when modeled as a linear program (LP). We define a condition on the simplicial complex called non total-unimodularity neutralized, or NTU neutralized, which ensures that even when the boundary matrix is not TU, the OHCP LP must contain an integral optimal vertex for every input chain. This condition is a property of K, and is independent of the input chain and the weights on the simplices. This condition is strictly weaker than the boundary matrix being TU. More interestingly, the polytope of the OHCP LP may not be integral under this condition. Still, an integral optimal vertex exists for every right-hand side, i.e., for every input chain. Hence a much larger class of OHCP instances can be solved in polynomial time than previously considered possible. As a special case, we show that 2-complexes with trivial first homology group are guaranteed to be NTU neutralized.
قيم البحث
اقرأ أيضاً
In this paper we develop further the multi-parameter model of random simplicial complexes. Firstly, we give an intrinsic characterisation of the multi-parameter probability measure. Secondly, we show that in multi-parameter random simplicial complexe
s the links of simplexes and their intersections are also multi-parameter random simplicial complexes. Thirdly, we find conditions under which a multi-parameter random simplicial complex is connected and simply connected.
We present the `Basic S* algorithm for computing shortest path through a metric simplicial complex. In particular, given a metric graph, $G$, which is constructed as a discrete representation of an underlying configuration space (a larger continuous
space/manifold typically of dimension greater than one), we consider the Rips complex, $mathcal{R}(G)$, associated with it. Such a complex, and hence shortest paths in it, represent the underlying metric space more closely than what the graph does. While discrete graph representations of continuous spaces is convenient for motion planning in configuration spaces of robotic systems, the metric induced in them by the ambient configuration space is significantly different from the metric of the configuration space itself. We remedy this problem using the simplicial complex representation. Our algorithm requires only an abstract graph, $G=(V,E)$, and a cost/length function, $d:Erightarrow mathbb{R}_+$, as inputs, and no global information such as an embedding or a global coordinate chart is required. The complexity of the Basic S* algorithm is comparable to that of Dijkstras search, but, as the results presented in this paper demonstrate, the shortest paths obtained using the proposed algorithm represent/approximate the geodesic paths in the original metric space significantly more closely.
We introduce a new algorithm for the structural analysis of finite abstract simplicial complexes based on local homology. Through an iterative and top-down procedure, our algorithm computes a stratification $pi$ of the poset $P$ of simplices of a sim
plicial complex $K$, such that for each strata $P_{pi=i} subset P$, $P_{pi=i}$ is maximal among all open subposets $U subset overline{P_{pi=i}}$ in its closure such that the restriction of the local $mathbb{Z}$-homology sheaf of $overline{P_{pi=i}}$ to $U$ is locally constant. Passage to the localization of $P$ dictated by $pi$ then attaches a canonical stratified homotopy type to $K$. Using $infty$-categorical methods, we first prove that the proposed algorithm correctly computes the canonical stratification of a simplicial complex; along the way, we prove a few general results about sheaves on posets and the homotopy types of links that may be of independent interest. We then present a pseudocode implementation of the algorithm, with special focus given to the case of dimension $leq 3$, and show that it runs in polynomial time. In particular, an $n$-dimensional simplicial complex with size $s$ and $nleq3$ can be processed in O($s^2$) time or O($s$) given one further assumption on the structure. Processing Delaunay triangulations of $2$-spheres and $3$-balls provides experimental confirmation of this linear running time.
In this paper, we study Formans discrete Morse theory in the context of weighted homology. We develop weight
In this paper we study the notion of critical dimension of random simplicial complexes in the general multi-parameter model described in our previous papers of this series. This model includes as special cases the Linial-Meshulam-Wallach model as wel
l as the clique complexes of random graphs. We characterise the concept of critical dimension in terms of various geometric and topological properties of random simplicial complexes such as their Betti numbers, the fundamental group, the size of minimal cycles and the degrees of simplexes. We mention in the text a few interesting open questions.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
