差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
| 直骨架的研究:introduction:preliminaries_and_definitions:the_motorcycle_graph [2025/09/25 12:03] – 张叶安 | 直骨架的研究:introduction:preliminaries_and_definitions:the_motorcycle_graph [2025/09/25 12:10] (当前版本) – 张叶安 | ||
|---|---|---|---|
| 行 4: | 行 4: | ||
| A motorcycle is a point moving with constant speed on a straight line. Let us consider $n$ motorcycles $m1, . . . , mn$, where each motorcycle $mi$ has its own constant velocity $v_i ∈ R_2$ and a start point $p_i ∈ R_2$ | A motorcycle is a point moving with constant speed on a straight line. Let us consider $n$ motorcycles $m1, . . . , mn$, where each motorcycle $mi$ has its own constant velocity $v_i ∈ R_2$ and a start point $p_i ∈ R_2$ | ||
| - | , with 1 ≤ i ≤ n. The trajectory ${pi + t · v_i : t ≥ 0}$ is called the track of $mi$. While a motorcycle moves it leaves a trace behind. When a motorcycle reaches the trace of another motorcycle then it stops driving — it crashes —, but its trace remains.Note that it is possible that motorcycles never crash. Following the terminology of Eppstein and Erickson [EE99] such motorcycles are said to have escaped. It is easy to see that there can be up to | + | , with 1 ≤ i ≤ n. The trajectory ${pi + t · v_i : t ≥ 0}$ is called the track of $mi$. While a motorcycle moves it leaves a trace behind. When a motorcycle reaches the trace of another motorcycle then it stops driving — it crashes —, but its trace remains. |
| - | (n2) intersections among the motorcycle tracks. However, no two motorcycle traces intersect in both interiors, which leads to at most $n$ intersections among the traces. | + | |
| - | 请注意，摩托车可能永远不会发生碰撞。按照 Eppstein 和 Erickson [EE99] 的术语，这样的摩托车被称为已经逃逸。很容易看出，摩托车轨迹之间最多可能有 (n2) 个交点。然而，没有两条摩托车轨迹在两个内部相交，这导致轨迹之间最多有 $n$ 个交点。 | + | 摩托车是在直线上匀速移动的点。 让我们考虑 $n$ 辆摩托车 |
| + | $m_1， . . . ， m_n$，其中每辆摩托车 $m_i$ 都有自己的恒定速度 $v_i ∈ R_2$ 和起点 $p_i ∈ R_2$，用 1 ≤ i ≤ n。 轨迹 | ||
| + | ${p_i + t · v_i ： t ≥ 0}$ 称为 $m_i$ 的轨迹 。 摩托车行驶时，会留下痕迹 。 当一辆摩托车到达另一辆摩托车的踪迹时，它就会停止行驶——它撞车—— 但它的痕迹仍然存在。 | ||
| + | |||
| + | Note that it is possible that motorcycles never crash. Following the terminology of Eppstein and Erickson [EE99] such motorcycles are said to have escaped. It is easy to see that there can be up to | ||
| + | (n^2) intersections among the motorcycle tracks. However, no two motorcycle traces intersect in both interiors, which leads to at most $n$ intersections among the traces. | ||
| + | |||
| + | |||
| + | 请注意，摩托车可能永远不会发生碰撞。按照 Eppstein 和 Erickson [EE99] 的术语，这样的摩托车被称为已经逃逸。很容易看出，摩托车轨迹之间最多可能有 (n^2) 个交点。然而，没有两条摩托车轨迹在两个内部相交，这导致轨迹之间最多有 $n$ 个交点。 | ||
| Definition 1.8 (motorcycle graph). The motorcycle graph M(m1, . . . , mn) of the motorcycles $m1, . . . , mn$ is defined by the arrangement of the motorcycles traces. | Definition 1.8 (motorcycle graph). The motorcycle graph M(m1, . . . , mn) of the motorcycles $m1, . . . , mn$ is defined by the arrangement of the motorcycles traces. | ||
| - | 定义 1.8 (摩托车图)[NT0]。) 摩托车 $m1, . . . , mn$ 的 motorcycle graph M(m1, . . . , mn) 定义为摩托车轨迹的排列。 | + | 定义 1.8 (摩托车图)[NT0]。) 摩托车 $m_1, . . . , m_n$ 的 motorcycle graph $M(m_1, . . . , m_n)$ 定义为摩托车轨迹的排列。 |
| In Figure 5 (a) we illustrate the motorcycle graph $M(m1, . . . , m10)$ of ten motorcycles. Cheng and Vigneron [CV07] presented a straight-skeleton algorithm for simple polygons $P$, which is based on the motorcycle graph, see Section 1.4.2.4. They first define a motorcycle graph induced by a polygon. The idea is that every reflex vertex | In Figure 5 (a) we illustrate the motorcycle graph $M(m1, . . . , m10)$ of ten motorcycles. Cheng and Vigneron [CV07] presented a straight-skeleton algorithm for simple polygons $P$, which is based on the motorcycle graph, see Section 1.4.2.4. They first define a motorcycle graph induced by a polygon. The idea is that every reflex vertex | ||
| $v$ of $P$ defines a motorcycle which starts at $v$ and has the same velocity as the wavefront vertex which corresponds to $v$. | $v$ of $P$ defines a motorcycle which starts at $v$ and has the same velocity as the wavefront vertex which corresponds to $v$. | ||
| - | 在图 5 (a) 中，我们展示了十辆摩托车的摩托车图 $M(m1, . . . , m10)$。Cheng 和 Vigneron [CV07] 提出了一个针对简单多边形 | + | 在图 5 (a) 中，我们展示了十辆摩托车的摩托车图 $M(m_1, . . . , m_10)$。Cheng 和 Vigneron [CV07] 提出了一个针对简单多边形 |
| $P$ 的直线骨架算法，该算法基于摩托车图，参见第 1.4.2.4 节。他们首先定义了一个由多边形诱导的摩托车图。其思想是，P 的每个凹顶点 | $P$ 的直线骨架算法，该算法基于摩托车图，参见第 1.4.2.4 节。他们首先定义了一个由多边形诱导的摩托车图。其思想是，P 的每个凹顶点 | ||
| $v$ 定义了一辆摩托车，该摩托车从 $v$ 开始，并具有与对应于 $v$ 的波前顶点相同的速度。 | $v$ 定义了一辆摩托车，该摩托车从 $v$ 开始，并具有与对应于 $v$ 的波前顶点相同的速度。 | ||
| 行 22: | 行 29: | ||
| non-degeneracy assumption Cheng and Vigneron [CV07] explicitly exclude the case that vertex events appear for the wavefront of $P$. The authors call this the non-degeneracy assumption. Eppstein and Erickson [EE99] remarked that perturbation techniques cannot be applied to transform these “degeneracies” to general cases. A small perturbation would change the straight skeleton drastically, | non-degeneracy assumption Cheng and Vigneron [CV07] explicitly exclude the case that vertex events appear for the wavefront of $P$. The authors call this the non-degeneracy assumption. Eppstein and Erickson [EE99] remarked that perturbation techniques cannot be applied to transform these “degeneracies” to general cases. A small perturbation would change the straight skeleton drastically, | ||
| - | 非退化假设 Cheng和Vigneron [CV07] 明确排除了顶点事件出现在$P$的波前的情况。作者称之为非退化假设。Eppstein和Erickson [EE99] 评论说，扰动技术不能应用于将这些“退化”转换为一般情况。一个小的扰动会极大地改变直线骨架，见第2.5.3节。另一方面，这种情况很可能发生，特别是当$P$包含共线边时。图1 显示了一个典型的例子。（我们将在第2.5节中介绍摩托车图到任意平面直线图的推广。）为了简单起见，我们通过非退化假设来指代稍微更一般的假设，即没有两辆摩托车同时相互碰撞。14 | + | 非退化假设 Cheng和Vigneron [CV07] 明确排除了顶点事件出现在$P$的波前的情况。作者称之为非退化假设。Eppstein和Erickson [EE99] 评论说，扰动技术不能应用于将这些“退化”转换为一般情况。一个小的扰动会极大地改变直线骨架，见第2.5.3节。另一方面，这种情况很可能发生，特别是当$P$包含共线边时。图1 显示了一个典型的例子。（我们将在第2.5节中介绍摩托车图到任意平面直线图的推广。）为了简单起见，我们通过非退化假设来指代稍微更一般的假设，即没有两辆摩托车同时相互碰撞。 |
| + | |||
| + | {{.: | ||
| + | |||
| + | Figure 5: Left: The motorcycle graph $M(m1, . . . , m10)$ of ten motorcycles. The velocities are represented by red arrows. Right: The motorcycle graph M(P), shown in red, induced by a simple polygon $P$ (bold). Each reflex vertex of $P$ emanates a motorcycle. | ||
| + | |||
| + | 图 5： 左图：十辆摩托车的摩托车图 M（m1， . . . ， m10）。 速度由红色箭头表示。右：摩托车图 M（P）， 以红色显示，由简单多边形 P（粗体）诱导。P 的每个反射顶点发出一辆摩托车。 | ||
| - | Figure 5: Left: The motorcycle graph $M(m1, . . . , m10)$ of ten motorcycles. The velocities are represented by red arrows. Right: The motorcycle graph M(P), shown in red, induced by a simple polygon $P$ (bold). Each reflex vertex of $P$ emanates a motorcycle.In order to guarantee the correctness of the algorithm of Cheng and Vigneron [CV07], it is necessary to assume that the motorcycles run out of fuel when they reach an edge of $P$. We cover this circumstance by introducing the alternative concept of walls. We assume that the plane contains straight-line segments which model rigid walls. If a motorcycle reaches a wall then it crashes and its trace remains. Following our terminology, | + | In order to guarantee the correctness of the algorithm of Cheng and Vigneron [CV07], it is necessary to assume that the motorcycles run out of fuel when they reach an edge of $P$. We cover this circumstance by introducing the alternative concept of walls. We assume that the plane contains straight-line segments which model rigid walls. If a motorcycle reaches a wall then it crashes and its trace remains. Following our terminology, |
| 为了保证Cheng和Vigneron算法[CV07]的正确性，有必要假设摩托车到达$P$的边缘时耗尽燃料。我们通过引入墙壁的替代概念来涵盖这种情况。我们假设该平面包含模拟刚性墙壁的直线段。如果摩托车到达墙壁，则会坠毁并留下痕迹。按照我们的术语，我们通过指定摩托车和墙壁来定义由多边形引起的摩托车图。 | 为了保证Cheng和Vigneron算法[CV07]的正确性，有必要假设摩托车到达$P$的边缘时耗尽燃料。我们通过引入墙壁的替代概念来涵盖这种情况。我们假设该平面包含模拟刚性墙壁的直线段。如果摩托车到达墙壁，则会坠毁并留下痕迹。按照我们的术语，我们通过指定摩托车和墙壁来定义由多边形引起的摩托车图。 | ||
张叶安