Name
Abstract | ||
|---|---|---|
We derive several algorithms for curves and surfaces represented using normal coordinates. The normal coordinate representation is a very succinct representation of curves and surfaces. For embedded curves, for example, its size is logarithmically smaller than a representation by edge intersections in a triangulation. Consequently, fast algorithms for normal representations can be exponentially faster than algorithms working on the edge intersection representation. Normal representations have been essential in establishing bounds on the complexity of recognizing the unknot [Hak61, HLP99, AHT02], and string graphs [SS驴02]. In this paper we present efficient algorithms for counting the number of connected components of curves and surfaces, deciding whether two curves are isotopic, and computing the algebraic intersection numbers of two curves. Our main tool are equations over monoids, also known as word equations. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/3-540-45655-4_40 | COCOON |
Keywords | Field | DocType |
edge intersection,edge intersection representation,succinct representation,algebraic intersection number,connected component,fast algorithm,normal curves,main tool,efficient algorithm,embedded curve,normal representation | Discrete mathematics,Combinatorics,Family of curves,Algebraic number,Algebraic curve,Computational geometry,Algorithm,Triangulation (social science),Geometric design,Unknot,Normal coordinates,Mathematics | Conference |
ISBN | Citations | PageRank |
3-540-43996-X | 8 | 0.60 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcus Schaefer | 1 | 123 | 12.63 |
| Eric Sedgwick | 2 | 142 | 14.38 |
| Daniel Stefankovic | 3 | 243 | 28.65 |