RESTRICTED-ORIENTATION CONVEXITY

Over a number of years my coworkers and I have been investigating different notions of convexity that have arisen in various applications of computational geometry. We began with ortho-convexity (in which an object is convex if its intersection with any vertical or any horizontal line is either empty or connected), studied north-west convexity that appears in two problems for transaction systems, and then began a more abstract approach to convexity defined with respect to a set of orientations. Because of the close relationship of convexity and visibility we explored the consequences of this more abstract view from the viewpoint of visibility. More recently we have begun to examine restricted-orientation convexity in higher dimensions.

  • [Refereed Journal Articles:]
    1. Ralf Hartmut Gueting. Stabbing C-oriented polygons. Information Processing Letters, 16:35-40, 1983.
    2. E. Soisalon-Soininen and D. Wood, Optimal algorithms to compute the closure of a set of iso-rectangles, Journal of Algorithms 5, (1984), 199-214.
    3. H. Edelsbrunner, J. van Leeuwen, Th. Ottmann, and D. Wood, Connected components of orthogonal geometric objects, RAIRO Informatique theorique 18, (1984), 171-183.
    4. Th. Ottmann, E. Soisalon-Soininen, and D. Wood, On the definition and computation of rectilinear convex hulls, Information Sciences 33,(1984), 157-171.
    5. G. J. E. Rawlins and D. Wood, On the optimal computation of finitely-oriented convex hulls, Information and Computation 72, (1987), 150-166.
    6. Th. Ottmann, E. Soisalon-Soininen, and D. Wood, Partitioning and separating sets of orthogonal polygons, Information Sciences 42, (1987), 31-49.
    7. G. J. E. Rawlins and D. Wood, A decomposition theorem for convexity spaces, Journal of Geometry 36, (1989), 143-159.
    8. G. J. E. Rawlins and D. Wood, Restricted-oriented convex sets, Information Sciences 54, (1991), 263-281.
    9. S. Schuierer and D. Wood, Staircase visibility and computation of kernels, Algorithmica 14, (1995), 1-26.
    10. E. Fink and D. Wood, Fundamentals of restricted-orientation convexity, Information Sciences 92, (1996), 175-196. Also appeared as Technical Report HKUST-CS95-46. HKUST-CS95-46.
    11. S. Schuierer and D. Wood, Visibility in Semi-Convex Spaces, Journal of Geometry 60, (1997), 160-187. Also appeared as Technical Report HKUST-CS95-39.
    12. E. Fink and D. Wood, Strong Restricted-Orientation Convexity, Geometriae Dedicata 69, (1998), 35-51. Also appeared as Technical Report HKUST-CS95-41.
    13. E. Fink and D. Wood. Generalized Halfspaces in Restricted-Orientation Convexity, Journal of Geometry 62, (1998), 99-120. Also appeared as Technical Report HKUST-CS95-45.
    14. S. Schuierer and D. Wood, Multiple Guard Kernels of Simple Polygons, Journal of Geometry 66, (1999), 161-186. Also appeared as Technical Report HKUST-CS95-39. An earlier version appeared as Technical Report IIF 37, University of Freiburg, 1991.
    15. E. Fink and D. Wood, Planar Strong Visibility, International Journal of Computational Geometry & Applications, (2003), to appear.

  • [Refereed Conference Presentations:]
    1. E. Soisalon-Soininen and D. Wood. An Optimal Algorithm for Testing for Safety and Detecting Deadlocks in Locked Transaction Systems, Proceedings of the ACM Symposium on Principles of Database Systems 1982, ACM Publication 475820 (1982), 108-116.
    2. G.J.E. Rawlins and D. Wood. Computational Geometry with Restricted Orientations, Proceedings of the 13th IFIP Conference on System Modelling and Optimization, Springer-Verlag Lecture Notes in Control and Information Sciences 113, (1988), 375-384.
    3. G.J.E. Rawlins, S. Schuierer, and D. Wood. Towards a General Theory of Visibility, Proceedings of the Second Canadian Computational Geometry Conference, (1990), 354-357.
    4. S. Schuierer, G.J.E. Rawlins, and D. Wood. A Generalization of Staircase Visibility, Proceedings of the Third Canadian Computational Geometry Conference, (1991), 96-99.
    5. S. Schuierer, G.J.E. Rawlins, and D. Wood. A Generalization of Staircase Visibility, in H. Bieri and H. Noltemeier (eds.), Computational Geometry---Methods, Algorithms, and Applications, Springer-Verlag Lecture Notes in Computer Science 553, (1991), 277-288.
    6. E. Fink and D. Wood, Three-dimensional strong convexity and visibility, Proceedings of the Vision Geometry IV Conference, (1995), 12 pages. Also appeared as Technical Report HKUST-CS95-33.
    7. E. Fink and D. Wood, Generalized halfspaces in restricted-orientation convexity. Fifth MSI-Stony Brook Workshop on Computational Geometry, Stony Brook, NY, (1995), 13 pages.
    8. E. Fink and D. Wood, Three-dimensional restricted-orientation convexity. Proceedings of the Twelveth European Workshop on Computational Geometry, Muenster, Germany, (1996), 12 pages.

  • [Books and Chapters in Books:]
    1. D. Wood, An isothetic view of computational geometry, in Computational Geometry, edited by G.T. Toussaint (Amsterdam: North-Holland Publishing Co., 1985), 429-459.
    2. G.J.E. Rawlins and D. Wood, Ortho-Convexity and its generalizations, in Computational Morphology, edited by G.T. Toussaint (Amsterdam: North-Holland Publishing Co., 1988), 137-152.
    3. G.J.E. Rawlins, S. Schuierer, and D.Wood, Convexity, visibility, and orthogonal polygons, in Vision Geometry, Contemporary Mathematics 119, edited by P. Bhattacharya, R.A. Melter, and A. Rosenfeld (Providence, RI: American Mathematical Society, 1991), 225-237.

  • [Miscellaneous Manuscripts:]
    1. E. Fink and D. Wood, Restricted-Orientation halfspaces, (1996), 11 pages.
    2. E. Fink and D. Wood, On generalized halfspaces, (1996), 14 pages.
    3. S. Schuierer and D. Wood, Restricted-orientation visibility, (1991), 92 pages; appeared as Technical Report IIF 40, University of Freiburg, 1991.
    4. V. Martynchik, N. Metelski, and D. Wood, O-Convexity: Computing Hulls, Approximations, and Orientation Sets, (1996), 5 pages.
  • [PhD theses:]
    1. Gregory J. E. Rawlins. Explorations in Restricted-Orientation Geometry. PhD thesis, University of Waterloo, 1987. University of Waterloo Computer Science Technical Report CS-89-48.
    2. Sven Schuierer. On Generalized Visibility. PhD thesis, University of Freiburg, Germany, 1991; appeared as three Technical Reports IIF 31, University of Freiburg, 1991; IIF 37, University of Freiburg, 1991; IIF 40, University of Freiburg, 1991.

    • Last updated by Derick Wood on June 4, 2003