1
00:00:06,800 --> 00:00:10,800
Most two-dimensional arrangements studied and computed to date are in the plane.
2
00:00:11,800 --> 00:00:15,800
However, we often need two-dimensional arrangements on curved surfaces.
3
00:00:18,100 --> 00:00:21,800
Consider for example, Gaussian maps of polytopes,
4
00:00:21,800 --> 00:00:25,800
which in turn can be used to compute Minkowski sums of polytopes.
5
00:00:27,200 --> 00:00:30,300
Here is a short sequence from an earlier movie that shows
6
00:00:30,300 --> 00:00:34,300
how such Minkowski sums can be computed using six planar
7
00:00:34,600 --> 00:00:38,600
arrangements embedded on the six facets of a cube.
8
00:00:39,600 --> 00:00:42,600
While this technique proved to be efficient, it generated
9
00:00:42,600 --> 00:00:46,000
additional vertices on the boundaries of the facets, and it
10
00:00:46,000 --> 00:00:49,700
required identifying matching vertices on the boundaries of
11
00:00:49,700 --> 00:00:51,600
abutting facets.
12
00:00:51,600 --> 00:00:55,300
The six planar arrangements are induced by linear segments,
13
00:00:55,300 --> 00:00:59,000
which can be handled with rational arithmetic.
14
00:00:59,000 --> 00:01:01,500
Naturally, a rival technique that uses an
15
00:01:01,500 --> 00:01:04,600
arrangement embedded on the sphere, eliminating the
16
00:01:04,600 --> 00:01:07,400
additional boundary vertices, but still content with
17
00:01:07,400 --> 00:01:10,700
rational arithmetic, has good chances to surpass its
18
00:01:10,700 --> 00:01:14,600
competition.
19
00:01:14,600 --> 00:01:17,300
Another example that demonstrates the usefulness of
20
00:01:17,300 --> 00:01:19,500
arrangements on curved surfaces is the need to construct
21
00:01:19,500 --> 00:01:23,300
and maintain arrangements induced by the intersections of
22
00:01:23,300 --> 00:01:27,300
one surface with a collection of other surfaces.
23
00:01:28,800 --> 00:01:31,900
We developed a general framework for computing arrangements
24
00:01:31,900 --> 00:01:35,900
on two-dimensional parametric surfaces, which applies to a
25
00:01:36,000 --> 00:01:39,900
variety of topologies including cylinder, torus, and
26
00:01:39,900 --> 00:01:42,300
sphere.
27
00:01:42,300 --> 00:01:44,500
It is based on the existing package that constructs
28
00:01:44,500 --> 00:01:48,500
and maintains planar arrangements.
29
00:01:48,700 --> 00:01:52,700
The domain is a rectangular two-dimensional parameter space with bottom,
30
00:01:53,400 --> 00:01:57,200
top, left, and right boundaries.
31
00:01:57,200 --> 00:02:01,200
An identification curve is a continuous curve, which is the mapping
32
00:02:01,400 --> 00:02:05,300
of opposite closed boundaries of the domain.
33
00:02:05,300 --> 00:02:09,300
A contraction point is a singular point, which is the mapping of
34
00:02:09,400 --> 00:02:13,400
a whole boundary of the domain.
35
00:02:13,600 --> 00:02:17,600
Code reuse is maximized by adapting the prevalent algorithms and
36
00:02:17,800 --> 00:02:21,800
their implementations. For example, efficient point-location.
37
00:02:23,400 --> 00:02:26,800
The generalized code handles features embedded on a modified
38
00:02:26,800 --> 00:02:30,800
surface defined over a modified parameter space, where the
39
00:02:31,300 --> 00:02:35,300
boundaries, identification curves, contraction points, and
40
00:02:35,800 --> 00:02:39,800
points at infinity, are removed.
41
00:02:40,000 --> 00:02:43,800
Specific code that handles features that approach or reach
42
00:02:43,800 --> 00:02:47,800
the boundaries is added to yield a complete implementation.
43
00:02:51,400 --> 00:02:54,800
As we sweep over the surface in order to construct a data
44
00:02:54,800 --> 00:02:58,500
structure describing the arrangement of the curves, we have
45
00:02:58,500 --> 00:03:02,200
to take into account the topology of the surface. Although
46
00:03:02,200 --> 00:03:06,200
we removed the boundary of the parameter space, we now have
47
00:03:06,300 --> 00:03:09,200
to account for the fact that several arcs pass through the
48
00:03:09,200 --> 00:03:13,200
north pole which is a contraction point. When the sweep
49
00:03:13,200 --> 00:03:16,400
line reaches the end of the parameter space, we have to
50
00:03:16,400 --> 00:03:19,600
glue the arrangement features on the sweep line with their
51
00:03:19,600 --> 00:03:22,400
counterparts that were discovered at the very beginning of
52
00:03:22,400 --> 00:03:25,000
the sweep.
53
00:03:25,000 --> 00:03:27,500
Most of the machinery developed in CGAL for planar
54
00:03:27,500 --> 00:03:31,400
arrangements can now be used with arrangements on surfaces
55
00:03:31,400 --> 00:03:34,400
provided that the user supplies the appropriate plug-ins
56
00:03:34,400 --> 00:03:38,100
for the specific topology of a surface and the geometry of
57
00:03:38,100 --> 00:03:41,500
the curves embedded on the surface. Here you see how two
58
00:03:41,500 --> 00:03:45,200
arrangements are overlaid on the sphere.
59
00:03:45,200 --> 00:03:48,600
The subdivision of the central sphere is the result of the
60
00:03:48,600 --> 00:03:52,600
overlay of other spherical arrangements around it.
61
00:03:55,400 --> 00:03:57,500
We can compute lower envelopes of
62
00:03:57,500 --> 00:04:00,700
surfaces over the sphere which in turn we use to compute
63
00:04:00,700 --> 00:04:04,700
Voronoi diagrams on the sphere. Here you can see an example,
64
00:04:04,800 --> 00:04:07,700
where the point sites are rendered in red, and the diagram
65
00:04:07,700 --> 00:04:11,300
is rendered in blue. The bisector of two point sites is a
66
00:04:11,300 --> 00:04:13,200
geodesic arc.
67
00:04:13,200 --> 00:04:17,100
Here you can see an example of a Power diagram on the sphere.
68
00:04:17,100 --> 00:04:21,100
In this case, the sites are circles rendered in red.
69
00:04:22,200 --> 00:04:26,200
The resulting diagrams are represented as arrangements and can
70
00:04:26,500 --> 00:04:30,500
passed as input to consecutive operations supported by the arrangement
71
00:04:31,100 --> 00:04:35,100
package. Here you can see the overlay of an arrangement induced by
72
00:04:35,300 --> 00:04:39,300
the continents and the Voronoi diagram of the first 9 cities that hosted
73
00:04:40,400 --> 00:04:44,400
the Symposium on Computational Geometry in this millenium.
74
00:04:44,800 --> 00:04:47,400
More details can be found in the paper Sweeping and
75
00:04:47,400 --> 00:04:51,400
Maintaining Two-Dimensional Arrangement on Surfaces: A
76
00:04:51,400 --> 00:04:55,400
First Step, which was presented at ESA 2007 or in the following websites.