Distance problems in computational with fixed orientations

Abstract

ln computational geometry, problems involving oily rectilinear objects with edges parallel to the x- aad y-axes have attracted twit attention. They are often easier to tohre (ha the tame problem∗ tor arbitrary objects, aad solutions ate of high practical value, lor iattaaee la VLSI detica. This b because in VLSI design technology requirements often dictate the use of only two orthogonal orientations for the bonndnry edfee of objects as well u wire∗. The restriction on the boundary edges motivates the stndy of rectilinear objects, while the restriction on wires brings the focus on the weD> known L,-metric (the Manhattan distance). In short, fir en the two orthogonal orieatatioas, both the shape of objects aad the distance taction are determiaed ia a aataral way. More recent VLSI fabrication techaolofy is capable of creatine edges aad wires in both the orthogonal aad diagonal orientations. This motiAvate! as to stndy more general polygons, aad to generalize the distance concept to the case where any Ixed set of orieatatioas is allowed. We iatrodace a family of aatnrally induced metrics, aad the snbeeqneat generalisation of geometrical concepts. A shortest connection between two points is ia this case a path composed of liae segments with only the given orientations. We derive optimal eolations tor vsrioas bask planar distance problems in this setting, sach as the computation of a Voioaoi diagram, a minim am spanning tree, aad the (minimnm aad maximum) distance between two coavex polygons. Maay other theAoretically interesting aad practically relevant problems remain to be solved. Ia particular, the new family of metrics may help bridge the gap between the L,- and the £t-metrics, as those are the limiting cases lor two aad inBnitely many regularly distributed orieatatioas.