Files

Action Filename Description Size Access License Resource Version
Show more files...

Abstract

Let M be a finite set of vectors in Rn of cardinality m and H(M) = {{x ∈ Rn : cTx = 0} : c ∈ M} the central hyperplane arrangement represented by M. An independent subset of M of cardinality n is called a Camion basis, if it determines a simplex region in the arrangementH(M). In this paper, we first present a new characterization of Camion bases, in the case where M is the column set of the node-edge incidence matrix (without one row) of a given connected digraph. Then, a general characterization of Camion bases as well as a recognition procedure which runs in O(n2m) are given. Finally, an algorithm which finds a Camion basis is presented. For certain classes of matrices, including totally unimodular matrices, it is proven to run in polynomial time and faster than the algorithm due to Fonlupt and Raco.

Details

Actions

Preview