Reconstruction of Parallel Line Segments From Endpoint Visibility Information.
Stephen Wismath · 1994
. In general, visibility reconstruction problems involve determining a set of objects in the plane that exhibit a specified set of visibility constraints. In this paper, an algorithm for reconstructing a set of parallel line segments is presented, from specified visibility information contained in an extended endpoint visibility graph. The algorithm runs in polynomial time and relies on simple vector arithmetic to generate a system of linear inequalities. 1. Introduction. There are many problems in computer science that are directly or indirectly concerned with the visibilities inherent among a collection of objects in the plane. Such problems arise in graphics, motion planning, computational geometry, and VLSI design, for example. Although the type of objects and the definition of visibility frequently vary, most results that deal explicitly with visibility issues focus on either the computational or structural properties of visibility. Given a set S of n disjoint line segments in the...