next up previous

Next: Monotonicity Issues Up: Projections Previous: Crossing-free Projections

Monotonic Projections

We arrive now at the main part of our survey, the monotonic projections.

Definition: A projection is said monotonic if all the directions of the edges are monotonically increasing in a specified direction on the projection plan.

Projections that preserve monotonicity of trees find applications in medical imaging. Let's think about arteries and veins, the visualisation is far more easy if they run in a single direction. Our purpose is to find projections which conserve this property of monotonicity in some directions and to identify them.

Our objects of interest at here are polygonal chains and trees, let's see what they look like.

Definition: A polygonal chain is set of line segments s1,s2,...,sn such that si is connected to si+1 at their common endpoint for i between 1 and n and two segments intersect each other only at their endpoints (s1 and sn do not intersect).

A polygonal chain, pc, is monotone if there exists a line L such that all lines l' perpendicular to L intersect pc at most once.

And for the trees:

Definition: A tree is a mathematical structure which can be viewed as either a graph or as a data structure. (here we deal with the tree graph.) A tree graph is a set of straight line segments connected at their ends containing no closed loops (cycles).

See more detailed definition on MathWorld or Wikipedia.

Finally, a polygonal chain or a tree may not admit a crossing free projection, but it may admit a projection which is monotonic in some direction. We can observe two projections of a vein on the following picture, and both have definitely a projection monotonic in one direction shown in red arrow.

We will see in the next chapter the main issues and complexity of finding monotonic projections.

next up previous

Contact us :

Jean HERBIERE and Yueyun SHU