An efficient output-sensitive algorithm for computing Boolean operations on circular-arc polygons and its applications.

        The boundaries of conic polygons consist of conic segments or second degree curves. The conic polygon has two degenerate or special cases: the linear polygon and the circular-arc polygon. The natural problem 鈥 boolean operation on linear polygons, has been extensively studied. Surprisingly, (almost) no article focuses on the problem of boolean operation on circular-arc polygons , which actually also has many applications. This implies that if there is a targeted solution for boolean operation on circular-arc polygons, it should be favourable for potential users. In this article, we close the gap by devising a concise data structure and then developing a targeted algorithm called R e2l . Our method is simple, easy-to-implement but without loss of efficiency. Given two circular-arc polygons with m m mathContainer Loading Mathjax and n n mathContainer Loading Mathjax edges respectively, our method runs in O(m+n+(l+k)logl) O ( m + n + ( l + k ) log l ) mathContainer Loading Mathjax time, using O(m+n+k) O ( m + n + k ) mathContainer Loading Mathjax space, where k k mathContainer Loading Mathjax is the number of intersections, and l l mathContainer Loading Mathjax is the number of related edges (defined in Section 5 ). Our algorithm has the power to approximate to linear complexity when k k mathContainer Loading Mathjax and l l mathContainer Loading Mathjax are small. The superiority of the proposed algorithm is also validated through empirical study. Particularly, our method is of independent interest, we show it can be easily extended to compute boolean operation of other types of polygons.