WORK PACKAGE 3
Restricted orientation geometry Details
Restricted orientation geometry studies geometric objects in Euclidean spaces, which comply with a set of properties related to some fixed set of lines. The most common example of such an object is a restricted oriented polygon [G83a, G84, G83], which is a polygon whose sides are parallel to the elements of a set of lines. Researchers have also considered restrictions of standard proximity and visibility [WWW87, S91], nontraditional notions of convexity [R87, FM09], and extensions of these definitions to high dimensional spaces [FW98]. Restricted orientation geometry is closely related to orthogonal geometry [MF82, NLLW83, OSW84], in which the set of lines is formed by the coordinate axes. Well known application areas of orthogonal geometry include polyhedra reconstruction [BG11], digital image shape analysis [DBBB11], and VLSI circuit layout design [UAR99]. Two application areas that are particularly promising are the following:
Restricted orientation convexity studies generalizations of traditional convexity based on the notion of restricted orientations. As of today, there exist several characterizations of convexity based on set-theoretical as well as functional definitions [FW04, MP98, FM09]. Among these, a generalization recently studied by CONNECT members is -convexity [AGRSU12, ASU13, AOSU14, AOSU15, PRSU13]. Given a set of lines through a common point, a region in the plane is said to be -convex if its intersections with all translations of any line in are either empty or connected. The -hull of P is suitable to be used as a separator or an enclosing shape. As it is always contained in the standard convex hull (and therefore, in several other traditional enclosing shapes), it is relevant in applications where the separator/enclosing shape is required to have minimum area, such as pattern recognition [RFCXKA04, DBBB11] and feature classification [KLV09, LKV11, SMBD15].
Given a set P of points in the plane, a rectilinear Steiner network (RSN) is a geometric graph with horizontal and vertical edges that has a vertex set P ∪ Ps, where the set Ps of Steiner points is such that P ∩ Ps = ∅. RSN-related problems usually define a connectivity requirement and an edge-cost function on the graph, and establish as a goal to find the set Ps that allows the graph to connect the elements in P, while minimizing the cost function. The most common example of a RSN-based problem is the Rectilinear Steiner Minimum Spanning Tree (RMST), where the graph is restricted to be a tree and the cost function is the sum of the edge lengths. The RMST gained much attention because of its applications in VLSI design and routing. Despite being NP-Complete [GJ77], exact algorithms have been designed for this problem and research is active to find efficient exponential algorithms for small instances, mainly because of few terminal configurations are typical in VLSI applications [G99]. Generalizations have also started to being explored, considering more than two fixed directions [BZ09].
