Reconstructing collections of arbitrary curves

ABSTRACT

The presented alg rithm rec nstructs collections of arbitrary curves (open, closed, smooth, with corners, with or without intersections). The algorithm is very simple and short and follows a novel and simple greedy strategy. The corner and intersection points are not required to but allowed to be in the sample. The described method works for curves in any dimension d asymptotically in O (n^2-1/d) time with involved data structures. Experiments show already a good performance with a very simple kd-tree structure.

REFERENCES

• 1: Sergei N. Bespamyatnikh, An optimal algorithm for closest pair maintenance (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.152-161, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220296]
• 2: Tamal K. Dey , Edgar A. Ramos , Kurt Mehlhorn, Curve reconstruction: connecting dots with good reason, Computational Geometry: Theory and Applications, v.15 n.4, p.229-244, April 2000 [doi>10.1016/S0925-7721(99)00051-6]
• 3: T. Lenz. Simple reconstruction of non-simple curves. Technical Report B 05-02, Freie Universitat Berlin, March 2005.
• 4: J. Matousek. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom., 10(2): 157--182, 1993.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
curve reconstruction, greedy, intersection