20130101
Computing covers of plane forests
Publication
Publication
Let φ be a function that maps any nonempty subset A of R2 to a nonempty subset φ(A) of R2. A φ cover of a set T = {T1, T2, . . . , Tm} of pairwise noncrossing trees in the plane is a set of pairwise disjoint connected regions such that 1. each tree Ti is contained in some region of the cover, 2. each region of the cover is either (a) φ(Ti) for some i, or (b) φ(A ∪ B), where A and B are constructed by either 2a or 2b, and A ∩ B ≠ φ. We present two properties for the function φ that make the φcover welldefined. Examples for such functions φ are the convex hull and the axisaligned bounding box. For both of these functions φ, we show that the φcover can be computed in O(n log2 n) time, where n is the total number of vertices of the trees in T.
Additional Metadata  

Conference  25th Canadian Conference on Computational Geometry, CCCG 2013 
Citation 
Barba, L. (Luis), Beingessner, A. (Alexis), Bose, P, & Smid, M. (2013). Computing covers of plane forests. Presented at the 25th Canadian Conference on Computational Geometry, CCCG 2013.
