On geometric representations of partially ordered sets
Paul J. Tanenbaum · 1995
Simple geometric objects such as points, line segments, and circles yield many interesting and challenging problems. We investigate several of the relationships among geometric objects of a given type in Euclidean d-space: point-halfspace containment; ball containment; coordinate-wise dominance; and, for d = 1, interval precedence and containment. Of particular interest is the interaction among several such relations on a common set of objects, a phenomenon that we call polysemy. We characterize the point-halfspace orders in R$\sp1$ along with several variants, present efficient algorithms to decide each of these classes and construct representations, and then prove that recognizing point-halfspace orders in R$\sp{d}$ is NP-hard for d $>$ 1. We show that for d $>$ 1 there exist d-ball orders of which every d-ball representation maps some minimal to a ball of nonzero radius. Then we investigate two types of poset polysemy. For the codominance pairs--pairs of posets that admit simultaneous dominance representations in the (x, y)- and ($-$x, y)-coordinate systems--we present a characterization along with linear-time decision and representation algorithms. Then we characterize the polysemic interval pairs--pairs of posets that admit simultaneous interval and interval-containment representations--and present algorithms to recognize them and construct representations. We conclude with a list of open problems and some further examples of polysemy.