Simple Reconstruction of Non-Simple Curves

Tobias Lenz
Institut für Informatik
Freie Universität Berlin
Takustr. 9, 14195 Berlin

Report B 05-02
March 2005

The presented algorithm reconstructs collections of arbitrary curves (open, closed, smooth, with corners, with or without intersections). The algorithm is very simple and short and has a novel and very simple sampling condition which guarantees correct results and does not need special adaption for regions close to corners, endpoints or intersections. 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(n2-1/d) time with involved data structures. Experiments show already a good performance with a very simple kd-tree structure.

Get the report here or by anonymous ftp:
File: pub/reports/