1
00:00:01,000 --> 00:00:09,000
This video presents a web application for the exact computation and visualization of algebraic arrangements. 

2
00:00:09,000 --> 00:00:15,000
By algebraic, we mean that the arrangement is induced by a set of algebraic curves.
 
3
00:00:15,000 --> 00:00:20,000
Each such curve is given as the vanishing set of an equation in two variables.

4
00:00:21,000 --> 00:00:27,500
Our demo program is available online, all computations are performed at a dedicated webserver.

5
00:00:28,500 --> 00:00:34,000
The user needs a web browser with a flash plug-in, no further installation process is required.

6
00:00:34,500 --> 00:00:37,000
Let's have a look at the user interface

7
00:00:39,500 --> 00:00:42,000
We start with an example of 4 curves of degree 4.

8
00:00:42,500 --> 00:00:46,000
With the analyze button, their arrangement is computed.

9
00:00:46,000 --> 00:00:48,500
The total number of features is shown on top,

10
00:00:48,500 --> 00:00:53,000
and more geometric information on every component is available.

11
00:00:53,500 --> 00:00:56,000
The plot button triggers the visualization method.

12
00:00:56,000 --> 00:01:02,500
The resulting picture displays the input curves accurately, and the exact topology is preserved.

13
00:01:02,500 --> 00:01:10,000
As demonstrated the interface allows to zoom into regions of the arrangement to explore its topology.

14
00:01:13,500 --> 00:01:18,000
To compute algebraic arrangements, we apply the Bentley-Ottmann sweep-line algorithm 

15
00:01:18,000 --> 00:01:22,000
to the case of arbitrary algebraic plane curves.

16
00:01:22,000 --> 00:01:26,500
All geometric predicates are reduced to a geometric-topological analysis 

17
00:01:26,500 --> 00:01:29,500
of a single curve  and of a pair of curves.

18
00:01:29,500 --> 00:01:35,500
The single curve analysis computes geometric information at the critical positions of the curve.

19
00:01:35,500 --> 00:01:41,500
The curve pair analysis captures the vertical ordering of two curves at critical positions.

20
00:01:41,500 --> 00:01:48,000
Recently, Eigenwillig, Kerber and Wolpert proposed algorithms for both types of analysis.

21
00:01:49,800 --> 00:01:55,000
In the visualization step, each x-monotone curve arc is rasterized separately,

22
00:01:48,000 --> 00:01:59,000
regardless of how close to its neighboring branches it resides.

23
00:01:59,000 --> 00:02:04,000
The curve-tracking algorithm starts with a seed point lying on a curve arc

24
00:02:04,000 --> 00:02:08,000
and traces the arc in both directions towards the end-points.

25
00:02:08,000 --> 00:02:12,000
At each iteration there are 8 possible directions to follow.

26
00:02:12,000 --> 00:02:18,000
Using range analysis and some heuristics one can quickly decide which direction to take.

27
00:02:18,000 --> 00:02:24,000
In case of a tie, the algorithm recursively subdivides a current pixel into 4 even parts,

28
00:02:24,000 --> 00:02:27,000
until the decision can be made unambiguously.

29
00:02:29,000 --> 00:02:31,000
Let's return to the web-site.

30
00:02:31,000 --> 00:02:35,000
The next example shows several curves from the same family.

31
00:02:35,000 --> 00:02:39,500
By plotting them, one can retrace the evolution of the family.

32
00:02:39,500 --> 00:02:43,000
We add more curves to create a highly-degenerate arrangement

33
00:02:43,000 --> 00:02:47,000
containing tangential intersections and vertical arcs.

34
00:02:47,000 --> 00:02:53,000
In this example, we now demonstrate more features of our web application.