关键词：
arrangements
robust computational geometry
摘要：
We present an arrangement algorithm for plane curves. The inputs are (1) continuous, compact, x-monotone curves and (2) a module that computes approximate crossing point of these curves, There are no general position requirements. We assume that the crossing module output is epsilon accurate, but allow it to be inconsistent, meaning that three curves anr in cyclic y order over an x interval. The curves are swept with a vertical line using the crossing module to compute and process sweep events. When the sweep detects an inconsistency, the algorithm breaks the cycle to obtain a linear order. We prove correctness in a realistic computational model of the crossing module. The number of vertice in the output is V = 2n+N+min (3kn, n(2)/2) and the running time is O(V log n) for n curves with N crossings and k inconsistencies. The output arrangement is realizable by curves that are O(epsilon+kn epsilon) close to the input curves, except in kn epsilon neighborhoods of the curve tails. The accuracy can be guaranteed everywhere by adding tiny horizontal extensions to the segment tails, but without the running time bound. An implementation is described for semi-algebraic curves based on a numerical equation solver. Experiments show that the extensions only slightly increase the running time and have little effect the output accuracy is close to epsilon, and the running time is close to that of the standard, non-robust floating point sweep.
欢迎来到三峡大学图书馆！
详细信息
