Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBlock Crossings in Storyline Visualizations
50
0
0.0
(
0
)
Added by
Fabian Lipp
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines. Our main results are as follows. We show that minimizing the number of block crossings is NP-hard, and we develop, for meetings of bounded size, a constant-factor approximation. We also present two fixed-parameter algorithms and, for meetings of size 2, a greedy heuristic that we evaluate experimentally.
rate research
Read More
Storyline visualizations show the structure of a story, by depicting the interactions of the characters over time. Each character is represented by an x-monotone curve from left to right, and a meeting is represented by having the curves of the participating characters run close together for some time. There have been various approaches to drawing storyline visualizations in an automated way. In order to keep the visual complexity low, rather than minimizing pairwise crossings of curves, we count block crossings, that is, pairs of intersecting bundles of lines. Partly inspired by the ILP-based approach of Gronemann et al. [GD 2016] for minimizing the number of pairwise crossings, we model the problem as a satisfiability problem (since the straightforward ILP formulation becomes more complicated and harder to solve). Having restricted ourselves to a decision problem, we can apply powerful SAT solvers to find optimal drawings in reasonable time. We compare this SAT-based approach with two exact algorithms for block crossing minimization, using both the benchmark instances of Gronemann et al. and random instances. We show that the SAT approach is suitable for real-world instances and identify cases where the other algorithms are preferable.
We consider the construction of a polygon $P$ with $n$ vertices whose turning angles at the vertices are given by a sequence $A=(alpha_0,ldots, alpha_{n-1})$, $alpha_iin (-pi,pi)$, for $iin{0,ldots, n-1}$. The problem of realizing $A$ by a polygon can be seen as that of constructing a straight-line drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied problem of constructing an emph{angle graph}. In 2D, we characterize sequences $A$ for which every generic polygon $Psubset mathbb{R}^2$ realizing $A$ has at least $c$ crossings, for every $cin mathbb{N}$, and describe an efficient algorithm that constructs, for a given sequence $A$, a generic polygon $Psubset mathbb{R}^2$ that realizes $A$ with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence $A$ can be realized by a (not necessarily generic) polygon $Psubset mathbb{R}^3$, and for every realizable sequence the algorithm finds a realization.
Given a colored point set in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color, either in its interior or on its boundary. Let $operatorname{rb-index}(S)$ denote the smallest size of a perfect rainbow polygon for a colored point set $S$, and let $operatorname{rb-index}(k)$ be the maximum of $operatorname{rb-index}(S)$ over all $k$-colored point sets in general position; that is, every $k$-colored point set $S$ has a perfect rainbow polygon with at most $operatorname{rb-index}(k)$ vertices. In this paper, we determine the values of $operatorname{rb-index}(k)$ up to $k=7$, which is the first case where $operatorname{rb-index}(k) eq k$, and we prove that for $kge 5$, [ frac{40lfloor (k-1)/2 rfloor -8}{19} %Birgit: leqoperatorname{rb-index}(k)leq 10 bigglfloorfrac{k}{7}biggrfloor + 11. ] Furthermore, for a $k$-colored set of $n$ points in the plane in general position, a perfect rainbow polygon with at most $10 lfloorfrac{k}{7}rfloor + 11$ vertices can be computed in $O(nlog n)$ time.
A graph drawn in the plane with n vertices is k-fan-crossing free for k > 1 if there are no k+1 edges $g,e_1,...e_k$, such that $e_1,e_2,...e_k$ have a common endpoint and $g$ crosses all $e_i$. We prove a tight bound of 4n-8 on the maximum number of edges of a 2-fan-crossing free graph, and a tight 4n-9 bound for a straight-edge drawing. For k > 2, we prove an upper bound of 3(k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.
Let $P$ be a set of $2n$ points in convex position, such that $n$ points are colored red and $n$ points are colored blue. A non-crossing alternating path on $P$ of length $ell$ is a sequence $p_1, dots, p_ell$ of $ell$ points from $P$ so that (i) all points are pairwise distinct; (ii) any two consecutive points $p_i$, $p_{i+1}$ have different colors; and (iii) any two segments $p_i p_{i+1}$ and $p_j p_{j+1}$ have disjoint relative interiors, for $i eq j$. We show that there is an absolute constant $varepsilon > 0$, independent of $n$ and of the coloring, such that $P$ always admits a non-crossing alternating path of length at least $(1 + varepsilon)n$. The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least $(1 + varepsilon)n$ points of $P$. This is a properly colored matching whose segments are pairwise disjoint and intersected by common line. For bo
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
