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.