On the Realizable Weaving Patterns of Polynomial Curves in R3

Basu, Saugata and Dhandapani, Raghavan and Pollack, Richard (2004) On the Realizable Weaving Patterns of Polynomial Curves in R3. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 36-42 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_5).

Full text not available from this repository.


We prove that the number of distinct weaving patterns produced by n semi-algebraic curves in ℝ3 defined coordinate-wise by polynomials of degrees bounded by some constant d, is bounded by 2 O(n log n), where the implied constant in the exponent depends on d. This generalizes a similar bound obtained by Pach, Pollack and Welzl [3] for the case when d=1.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_5
Classifications:Z Theory > Z.250 Geometry
ID Code:565

Repository Staff Only: item control page


N. Alon, J. Pach, R. Pinchasi, R. Radoicic, M. Sharir, Crossing Patterns of Semi-algebraic Sets, Preprint.

S. Basu, R. Pollack, M.-F. Roy, Algorithms in Real Algebraic Geometry, Springer-Verlag, 2003.

J. Pach, R. Pollack, E. Welzl, Weaving Patterns of Lines and Line Segments in Space, Algorithmica, 9:561-571, 1993.