تقرير
Some fast algorithms for curves in surfaces
| العنوان: | Some fast algorithms for curves in surfaces |
|---|---|
| المؤلفون: | Lackenby, Marc |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Geometric Topology, Computer Science - Computational Geometry, 57K20 |
| الوصف: | We present some algorithms that provide useful topological information about curves in surfaces. One of the main algorithms computes the geometric intersection number of two properly embedded 1-manifolds $C_1$ and $C_2$ in a compact orientable surface $S$. The surface $S$ is presented via a triangulation or a handle structure, and the 1-manifolds are given in normal form via their normal coordinates. The running time is bounded above by a polynomial function of the number of triangles in the triangulation (or the number of handles in the handle structure), and the logarithm of the weight of $C_1$ and $C_2$. This algorithm represents an improvement over previous work, since its running time depends polynomially on the size of the triangulation of $S$ and it can deal with closed surfaces, unlike many earlier algorithms. Another algorithm, with similar bounds on its running time, can determine whether $C_1$ and $C_2$ are isotopic. We also present a closely related algorithm that can be used to place a standard 1-manifold into normal form. Comment: 44 pages, 16 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2401.16056 |
| رقم الأكسشن: | edsarx.2401.16056 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |