A natural metric in 2-manifold surfaces is to use geodesic distance. If a 2-manifold surface is represented by a triangle mesh T , the geodesic metric on T can be computed exactly using computational geometry methods. Previous work for establishing the geodesic metric on T only supports using half-edge data structures; i.e., each edge e in T is split into two halves (he1, he2) and each half-edge corresponds to one of two faces incident to e. In this paper, we prove that the exact-geodesic structures on two halfedges of e can be merged into one structure associated with e. Four merits are achieved based on the properties which are studied in this paper: (1) Existing CAD systems that use edge-based data structures can directly add the geodesic distance function without changing the kernel to a half-edge data structure; (2) To find the geodesic path from inquiry points to the source, the MMP algorithm can be run in an onthe- fly fashion such that the inquiry points are covered by correct wedges; (3) The MMP algorithm is sped up by pruning unnecessary wedges during the wedge propagation process; (4) The storage of the MMP algorithm is reduced since fewer wedges need to be stored in an edge-based data structure. Experimental results show that when compared to the classic half-edge data structure, the edge-based implementation of the MMP algorithm reduces running time by 44% and storage by 29% on average.

No abstract uploaded!

No abstract uploaded!

In 1975, P. Erd\"{o}s proposed the problem of determining the maximum number $f(n)$ of edges in a graph of $n$ vertices in which any two cycles are of different lengths. In this paper, it is proved that $$f(n)\geq n+36t$$ for $t=1260r+169 \,\ (r\geq 1)$ and $n \geq 540t^{2}+\frac{175811}{2}t+\frac{7989}{2}$. Consequently, $\liminf\sb {n \to \infty} {f(n)-n \over \sqrt n} \geq \sqrt {2 + {2 \over 5}},$ which is better than the previous bounds $\sqrt 2$ (see [2]), $\sqrt {2+{2562\over 6911}}$ (see [7]).

Recently, Tsai-Tseng-Yau constructed new invariants of symplectic manifolds: a sequence of A-infinity algebras built of differential forms on the symplectic manifold. We show that these symplectic A-infinity algebras have a simple topological interpretation. Namely, when the cohomology class of the symplectic form is integral, these A-infinity algebras are equivalent to the standard de Rham differential graded algebra on certain odd dimensional sphere bundles over the symplectic manifold. From this equivalence, we deduce for a closed symplectic manifold that Tsai-Tseng-Yau's symplectic A-infinity algebras satisfy the Calabi-Yau property, and importantly, that they can be used to define an intersection theory for coisotropic/isotropic chains. We further demonstrate that these symplectic A-infinity algebras satisfy several functorial properties and lay the groundwork for addressing Weinstein functoriality and invariance in the smooth category.