Characterization and Recognition of Point-Halfspace and Related Orders (Preliminary Version)

Tanenbaum, Paul J. and Goodrich, Michael T. and Scheinerman, Edward R. (1995) Characterization and Recognition of Point-Halfspace and Related Orders (Preliminary Version). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 234-245(Official URL: http://dx.doi.org/10.1007/3-540-58950-3_375).

Full text not available from this repository.

Abstract

We characterize four classes of geometric membership and containment orders-structurally and in terms of forbidden subposets-and present linear- or near linear-time recognition algorithms for each class. We also show that recognizing point-halfspace orders in \mathbb{R}^{d} is NP-hard for d \geq 2.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-58950-3_375
Classifications: Z Theory > Z.250 Geometry
G Algorithms and Complexity > G.560 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/167

Actions (login required)

View Item View Item