Abstract
It is shown that for every finite set of disjoint convex polygonal obstacles in the plane, with a total of n vertices, the free space around the obstacles can be partitioned into open convex cells whose dual graph (defined below) is 2-edge connected. Intuitively, every edge of the dual graph corresponds to a pair of adjacent cells that are both incident to the same vertex.
Aichholzer et al. recently conjectured that given an even number of line-segment obstacles, one can construct a convex partition by successively extending the segments along their supporting lines such that the dual graph is the union of two edge-disjoint spanning trees. Here we present counterexamples to this conjecture, with n disjoint line segments for any n≥15, such that the dual graph of any convex partition constructed by this method has a bridge edge, and thus the dual graph cannot be partitioned into two spanning trees.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aichholzer O, Bereg S, Dumitrescu A, García A, Huemer C, Hurtado F, Kano M, Márquez A, Rappaport D, Smorodinsky S, Souvaine D, Urrutia J, Wood D (2009) Compatible geometric matchings. Comput Geom 42:617–626
Andrzejak A, Aronov B, Har-Peled S, Seidel R, Welzl E (1998) Results on k-sets and j-facets via continuous motion. In: Proc 14th Sympos Comput Geom. ACM, New York, pp 192–199
Banchoff TF (1974) Global geometry of polygons I: The theorem of Fabricius–Bjerre. Proc Am Math Soc 45:237–241
Benbernou N, Demaine ED, Demaine ML, Hoffmann M, Ishaque M, Souvaine DL, Tóth CD (2007) Disjoint segments have convex partitions with 2-edge connected dual graphs. In: Proc Canadian Conf Comput Geom, pp 13–16
Benbernou N, Demaine ED, Demaine ML, Hoffmann M, Ishaque M, Souvaine DL, Tóth CD (2008) Erratum for “Disjoint segments have convex partitions with 2-edge connected dual graphs”. In: Proc Canadian Conf Comput Geom, p 223
Bentley JL, Ottmann TA (1979) Algorithms for reporting and counting geometric intersections. IEEE Trans Comput C 28(9):643–647
Bose P, Houle ME, Toussaint GT (2001) Every set of disjoint line segments admits a binary tree. Discrete Comput Geom 26(3):387–410
Carlsson JG, Armbruster B, Ye Y (2009) Finding equitable convex partitions of points in a polygon efficiently. ACM Trans Algorithms (to appear)
Chazelle B, Dobkin DP (1985) Optimal convex decompositions. Comput Geom 2:63–133
Grantson M, Levcopoulos C (2005) A fixed parameter algorithm for the minimum number convex partition problem. In: Proc Japan Conf Discrete Comput Geom, Tokyo, 2004. LNCS, vol 3746. Springer, Berlin, pp 83–94
Ishaque M, Speckmann B, Tóth CD (2009) Shooting permanent rays among disjoint polygons in the plane. In: Proc 25th Sympos Comput Geom. ACM, New York, pp 51–60
Kaneko A, Kano M (2002) Perfect partitions of convex sets in the plane. Discrete Comput Geom 28(2):211–222
Keil M (2000) Polygon decomposition. In: Sack J-R, Urrutia J (eds) Handbook of computational geometry. Elsevier, Amsterdam, pp 491–518
Keil M, Snoeyink J (2002) On the time bound for convex decomposition of simple polygons. Int J Comput Geom Appl 12:181–192
Knauer C, Spillner A (2006) Approximation algorithms for the minimum convex partition problem. In: Proc SWAT. LNCS, vol 4059. Springer, Berlin, pp 232–241
Krumme DW, Rafalin E, Souvaine DL, Tóth CD (2008) Tight bounds for connecting sites across barriers. Discrete Comput Geom 40(3):377–394
Lien J-M, Amato NM (2006) Approximate convex decomposition of polygons. Comput Geom 35(1–2):100–123
Lingas A (1982) The power of non-rectilinear holes. In: Proc 9th ICALP. LNCS, vol 140. Springer, Berlin, pp 369–383
Streinu I (2005) Pseudo-triangulations, rigidity and motion planning. Discrete Comput Geom 34(4):587–635
Tan G, Bertier M, Kermarrec A-M (2009) Convex partition of sensor networks and its use in virtual coordinate geographic routing. In: Proc INFOCOM. IEEE Comput Soc, Los Alamitos, pp 1746–1754
Tóth CD (2003) Guarding disjoint triangles and claws in the plane. Comput Geom 25(1–2):51–65
Author information
Authors and Affiliations
Corresponding author
Additional information
This material is based upon work supported by the National Science Foundation under Grant No. CCF-0431027 and CCF-0830734, Tufts Provost’s Summer Scholars Program, and NSERC grant RGPIN 35586. Research was done at Tufts University.
Rights and permissions
About this article
Cite this article
Al-Jubeh, M., Hoffmann, M., Ishaque, M. et al. Convex partitions with 2-edge connected dual graphs. J Comb Optim 22, 409–425 (2011). https://doi.org/10.1007/s10878-010-9310-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-010-9310-1