Search

We revisit the classical problem of computing the contour tree of a scalar field $$f:\mathbb {M}\rightarrow \mathbb {R}$$ , where $$\mathbb {M}$$ is a triangulation of a ball in $$\mathbb {R}^d$$ . The contour tree is a fundamental topological structure that tracks the evolution of level sets of f and has numerous applications in data analysis and visualization. All existing algorithms begin with a global sort of at least all critical values of f, which can require (roughly) $$\Omega (n\log n)$$ time, where n is the number of vertices of the mesh. Existing lower bounds show that there are pathological instances where this sort is required. We present the first algorithm whose time complexity depends on the contour tree structure, and avoids the global sort for non-pathological inputs. (We assume that the Morse degree of the function f at any point is at most 3.) If C denotes the set of critical points in $$\mathbb {M}$$ , the running time is roughly $$O(N+\sum _{v \in C} \log \ell _v)$$ , where $$\ell _v$$ is the depth of v in the contour tree and N is the total complexity of $$\mathbb {M}$$ . This matches all existing upper bounds, but is a significant asymptotic improvement when the contour tree is short and fat. Specifically, our approach ensures that any comparison made is between nodes that are either adjacent in $$\mathbb {M}$$ or in the same descending path in the contour tree, allowing us to argue strong optimality properties of our algorithm. Our algorithm requires several novel ideas: partitioning $$\mathbb {M}$$ in well-behaved portions, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis. [ABSTRACT FROM AUTHOR]

Given n points in the plane, a covering path is a polygonal path that visits all the points. If no three points are collinear, every covering path requires at least n/2 segments, and n−1 straight line segments obviously suffice even if the covering path is required to be noncrossing. We show that every set of n points in the plane admits a (possibly self-crossing) covering path consisting of n/2+ O( n/log n) straight line segments. If the path is required to be noncrossing, we prove that (1− ε) n straight line segments suffice for a small constant ε>0, and we exhibit n-element point sets that require at least 5 n/9− O(1) segments in every such path. Further, the analogous question for noncrossing covering trees is considered and similar bounds are obtained. Finally, it is shown that computing a noncrossing covering path for n points in the plane requires Ω( nlog n) time in the worst case. [ABSTRACT FROM AUTHOR]

A simple topological graph$$T=(V(T), E(T))$$ T = ( V ( T ) , E ( T ) ) is a drawing of a graph in the plane where every two edges have at most one common point (an endpoint or a crossing) and no three edges pass through a single crossing. Topological graphs $$G$$ G and $$H$$ H are isomorphic if $$H$$ H can be obtained from $$G$$ G by a homeomorphism of the sphere, and weakly isomorphic if $$G$$ G and $$H$$ H have the same set of pairs of crossing edges. We generalize results of Pach and Tóth and the author’s previous results on counting different drawings of a graph under both notions of isomorphism. We prove that for every graph $$G$$ G with $$n$$ n vertices, $$m$$ m edges and no isolated vertices the number of weak isomorphism classes of simple topological graphs that realize $$G$$ G is at most $$2^{O(n^2\log (m/n))}$$ 2 O ( n 2 log ( m / n ) ) , and at most $$2^{O(mn^{1/2}\log n)}$$ 2 O ( m n 1 / 2 log n ) if $$m\le n^{3/2}$$ m ≤ n 3 / 2 . As a consequence we obtain a new upper bound $$2^{O(n^{3/2}\log n)}$$ 2 O ( n 3 / 2 log n ) on the number of intersection graphs of $$n$$ n pseudosegments. We improve the upper bound on the number of weak isomorphism classes of simple complete topological graphs with $$n$$ n vertices to $$2^{n^2\cdot \alpha (n)^{O(1)}}$$ 2 n 2 · α ( n ) O ( 1 ) , using an upper bound on the size of a set of permutations with bounded VC-dimension recently proved by Cibulka and the author. We show that the number of isomorphism classes of simple topological graphs that realize $$G$$ G is at most $$2^{m^2+O(mn)}$$ 2 m 2 + O ( m n ) and at least $$2^{\Omega (m^2)}$$ 2 Ω ( m 2 ) for graphs with $$m>(6+\varepsilon )n$$ m > ( 6 + ε ) n . [ABSTRACT FROM AUTHOR]