Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 41 (2000), No. 1, 181-193.

The Concept of Cutting Vectors for Vector Systems in the Euclidean Plane

Günter Heinz

Fakultät für Mathematik, Technische Universität Chemnitz D-09107 Chemnitz, Germany

Abstract. The concept of cutting vectors is introduced to study the combinatorial structure of vector configurations in the plane. We give a full characterization of those n-tuples of integers which are realizable as cutting vector. Furthermore, ‘simple’ mappings are defined that transform cutting vectors into each other. Thus it becomes possible to consider all combinatorial types of vector systems.

0. Introduction

In the context of combinatorial and computational geometry often occur vector systems, e.g., as normal vectors of hyperplanes in the Euclidean or projective d-space.

Starting with Grünbaum [6], vector systems of hyperplanes became a basic subject. Edelsbrunner [4] and others developed algorithms for computational treatments. In recent years the theory of oriented matroids has been developed [2], [5], [1], [3]. Arrangements of oriented hyperplanes may be viewed as realizations of oriented matroids. In general, arrangements yield affine sign vector systems, which have been studied extensively by Karlander [8].

In [9] and [10] Linhart has shown that in E^{2} interesting questions still are open, and that it is natural to use a ‘geometric language’.

In this paper the concept of ‘cutting vectors’ is developed to code the combinatorial structure of systems of unit vectors in E^{2} . In order to consider all possible combinatorial types of vector systems it is important to characterize the cutting vectors and to show how to ‘move’ in the system of cutting vectors (of a fixed number of components). This is done in Theorem 2.2 and Theorem 3.7.

In [7] we will use the concept of cutting vectors to derive results on the total weight of arrangements.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2000 Heldermann Verlag

1. Basic notation

A finite collection of n ≥ 2 unit vectors in the Euclidean plane E^{2} is called a vector system. Let V = {v_{1}, …, v_{n}} be such a vector system.

The angle < ) (v_{i}, v_{j}) is measured from v_{i} to v_{j} in the range [0, 2π) in mathematically positive sense. We assume that the vectors are labelled according to mathematically positive sense, i.e., it holds that

0 < < ) (v_{1}, v_{j}) < < ) (v_{1}, v_{j′}) ⇔ 1 < j < j′.  (1.1)

For each v_{i} ∈ V we determine the cardinality

k_{i} := card {v ∈ V : 0 < < ) (v_{i}, v) < π}

and the set

V_{i} := \{ \begin{matrix}∅ & if & k_{i} = 0 \\ \{v_{i+1}, …, v_{i+k_{i}}\} & else. \end{matrix}

2. The concept of cutting vectors

Let V = {v_{1}, …, v_{n}} be a vector system, then there exists a vector k = (k_{1}, …, k_{n}) ∈ ℕ^{n} uniquely determined by the cardinalities k_{i} in the previous section. This vector is called the cutting vector of the vector system V. It characterizes the combinatorial structure of the vector system up to cyclic permutations, i.e., cyclic permutations of the cutting vector correspond to appropriate relabelings of the vectors and, consequently, preserve the combinatorial properties of the vector system.

Furthermore, we define the cutting matrix C = (c_{ij}) by

c_{ij} := sign det (v_{i}, v_{j}) ∈ {+, −, 0}.

This is essentially the same as the chirotope of the considered vector system [1]. It follows that

c_{ij} = \{ \begin{matrix}0 & for & j = i \\ + & for & j = i + 1, …, i + k_{i}  if k_{i} ≠ 0 \\ 0 & for & j = i + k_{i} + 1  if v_{i+k_{i}+1} = −v_{i} \\ − & for & j = i + k_{i} + 1  if v_{i+k_{i}+1} ≠ −v_{i} ∧ k_{i} ≤ n − 2 \\ − & for & j = i + k_{i} + 2, …, i + n − 1 if k_{i} ≤ n − 3 \end{matrix}

(the expressions of the index j are taken modulo n).

Lemma 2.1. Let k = (k_{1}, …, k_{n}) be the cutting vector of the vector system V, and γ be the number of pairs of oppositely directed vectors in V. Then

c ∑_{i=1}^{n} k_{i} = \frac{1}{2}n(n − 1) − γ.  (2.1)

Proof. Let c_{i} := (c_{i1}, …, c_{in}) be the i-th row of the matrix C and φ_{i} the number of ‘+’ in c_{i}. Then φ_{i} = k_{i}.

Let c^{i} := (c_{1i}, …, c_{ni})^{T} be the i-th column of C and ψ_{i} the number of ‘+’ in c^{i}. Then

ψ_{i} = \{ \begin{matrix}n − k_{i} − 2 & if v_{i} and v_{i+k_{i}+1} are oppositely directed \\ n − k_{i} − 1 & otherwise. \end{matrix}

Consequently, ∑_{i=1}^{n}(φ_{i} + ψ_{i}) = n(n − 1) − 2γ. On the other hand, if κ denotes the number

of ‘+’ in C, then κ = ∑_{i=1}^{n} φ_{i} = ∑_{i=1}^{n} ψ_{i}. Thus, we have κ = ∑_{i=1}^{n} φ_{i} = ∑_{i=1}^{n} k_{i} and

κ = \frac{1}{2} (∑_{i=1}^{n} φ_{i} + ∑_{i=1}^{n} ψ_{i}) = \frac{1}{2} ∑_{i=1}^{n}(φ_{i} + ψ_{i}) = \frac{1}{2}n(n − 1) − γ.  □

Now we consider the question for the realizability as cutting vector:

Given a vector a = (a_{1}, …, a_{n}) ∈ ℕ^{n}. Under which conditions do there exist vector systems with cutting vector a?

We can give an answer to this question by a characterization of cutting vectors (again all indices are taken modulo n):

Theorem 2.2. The vector a = (a_{1}, …, a_{n}) ∈ ℕ^{n} is realizable as cutting vector of vector systems if and only if the following system of inequalities is valid for i = 1, …, n:

0 ≤ a_{i} ≤ n − 1,  (2.2)
a_{i} ≤ a_{i+1} + 1,  (2.3)
a_{i+a_{i}} ≤ n − a_{i} − 1,  (2.4)
a_{i+a_{i}+1} ≥ n − a_{i} − 2,  (2.5)
a_{i+a_{i}+2} ≥ n − a_{i} − 2.  (2.6)

Equality in (2.5) holds if and only if the vectors v_{i} and v_{i+a_{i}+1} are oppositely directed.

Proof.

(1) Let a = (a_{1}, …, a_{n}) be the cutting vector of a vector system V.

(a) (2.2) follows from the definition of cutting vectors.

(b) (2.3) holds true for a_{i} = 0 and a_{i} = 1. If a_{i} ≥ 2, then from c_{i,i+a_{i}} = + it follows that c_{i+1,i+a_{i}} = +. From

< ) (v_{i+1}, v_{i+a_{i}}) < π ⇔ v_{i+a_{i}} ∈ V_{i+1} ⇔ c_{i+1,i+a_{i}} = +

we get a_{i+1} ≥ a_{i} − 1, which proves (2.3).

(c) (2.4) holds true for a_{i} = 0.

If a_{i} ≥ 1, then from c_{i,i+a_{i}} = + it follows that c_{i+a_{i},i} = −. Consequently, i + a_{i} + a_{i+a_{i}} + 1 ≤ n + i, which proves (2.4).

(d) (2.5) holds true for a_{i} = n − 1. If c_{i,i+a_{i}+1} = 0, then it follows that c_{i+a_{i}+1,i} = 0. Consequently, if a_{i} ≠ n − 1, then i + a_{i} + 1 + a_{i+a_{i}+1} = n + i − 1, and

a_{i+a_{i}+1} = n − a_{i} − 2.

If c_{i,i+a_{i}+1} = −, then it follows that c_{i+a_{i}+1,i} = +. Consequently, i + a_{i} + 1 + a_{i+a_{i}+1} ≥ n + i, which proves (2.5).

(e) (2.6) holds true for a_{i} = n − 1 and a_{i} = n − 2. If a_{i} ≤ n−3, then c_{i,i+a_{i}+2} = − and c_{i+a_{i}+2,i} = +. Consequently, i+a_{i}+2+a_{i+a_{i}+2} ≥ n + i, which proves (2.6).

(2) Let a = (a_{1}, …, a_{n}) ∈ ℕ^{n} satisfy the conditions (2.2)–(2.6). We construct a vector system with cutting vector a.

(a) Let v_{1} be an arbitrary unit vector in E^{2}. If a_{1} = 0, then we set V_{1} := ∅. It is easy to find a second unit vector v_{2} satisfying < ) (v_{1}, v_{2}) ≥ π. If a_{1} ≠ 0, then it is easy to find a set V_{1} = {v_{2}, …, v_{1+a_{1}}} of unit vectors satisfying (1.1) and 0 < < ) (v_{1}, v) < π ∀v ∈ V_{1}.

(b) Assume that

V_{i} = \{ \begin{matrix}∅ & if & a_{i} = 0 \\ \{v_{i+1}, …, v_{i+a_{i}}\} & else \end{matrix}

satisfies (1.1) and 0 < < ) (v_{i}, v) < π ∀ v ∈ V_{i}. If a_{i} ≥ 2, then from < ) (v_{i}, v_{i+a_{i}}) < π it follows that

< ) (v_{i+1}, v_{j}) < π for j = i + 2, …, i + a_{i},

and we may define the set

Ṽ_{i+1} := \{ \begin{matrix}∅ & if & a_{i} < 2 \\ \{v_{i+2}, …, v_{i+a_{i}}\} & else. \end{matrix}

If a_{i} = a_{i+1} + 1, then we get i + a_{i} = (i + 1) + a_{i+1}. Consequently, we can set

V_{i+1} := \{ \begin{matrix}∅ & if & a_{i+1} = 0 \\ Ṽ_{i+1} & else. \end{matrix}

If a_{i} < a_{i+1} + 1, then we get i + a_{i} < (i + 1) + a_{i+1}.

We consider the two cases:

(b_{1}) If (i + 1) + a_{i+1} < n, then we find a set

V′_{i+1} = \{ \begin{matrix}∅ & if & a_{i+1} = 0 \\ \{v_{i+a_{i}+1}, …, v_{i+1+a_{i+1}}\} & else, \end{matrix}

of unit vectors satisfying

< ) (v_{i+1}, v_{j}) < π, < ) (v_{i}, v_{j}) ≥ π for v_{j} ∈ V′_{i+1}.

Then

V_{i+1} := Ṽ_{i+1} ∪ V′_{i+1}

satisfies (1.1), 0 < < ) (v_{i+1}, v) < π ∀ v ∈ V_{i+1}, and this inequality fails for v ∈ {v_{1}, …, v_{i+1}}.

(b_{2}) If (i + 1) + a_{i+1} = n + α, α ≥ 0, then we find a set

V′_{i+1} = \{ \begin{matrix}∅ & if & a_{i+1} = 0 \\ \{v_{i+a_{i}+1}, …, v_{n}\} & else, \end{matrix}

of unit vectors satisfying the analogous conditions like in (b_{1}). Furthermore, from (2.4) it follows that

α + a_{α} = (i + 1) + a_{i+1} − n + a_{i+1+a_{i+1}} ≤ i.

Consequently, v_{i+1} ∉ V_{α}. Now we define the set

V′′_{i+1} := \{ \begin{matrix}∅ & if & α = 0 \\ \{v_{1}, …, v_{α}\} & else. \end{matrix}

Then

V_{i+1} := Ṽ_{i+1} ∪ V′_{i+1} ∪ V′′_{i+1}

satisfies (1.1) and 0 < < ) (v_{i+1}, v) < π ∀ v ∈ V_{i+1}. We still have to prove that the inequality fails for v ∈ {v_{α+1}, …, v_{i+1}}, i.e., α is maximal or, equivalently, v_{α+1} ∉ V_{i+1}. From (i + 1) + a_{i+1} = n + α it follows that

α = (i + 1) + a_{i+1} − n ≤ (i + 1) + (n − 1) − n = i .

If α = i, then < ) (v_{i+1}, v_{α+1}) = 0. If α < i, then we consider two cases: If equality holds in (2.5), then from

V_{α+1} = {v_{α+2}, …, v_{α+1+a_{α+1}}}

and

α + 1 + a_{α+1} = (i + 1) + a_{i+1} − n + 1 + a_{i+1+a_{i+1}+1} = i

it follows that v_{i+1} ∉ V_{α+1}, which is equivalent to < ) (v_{α+1}, v_{i+1}) ≥ π. On the other hand, from

V_{i+1} = {v_{i+2}, …, v_{i+1+a_{i+1}}}

and i + 1 + a_{i+1} + 1 = n + α + 1 it follows that

< ) (v_{i+1}, v_{α+1}) ≥ π.

The two inequalities yield < ) (v_{i+1}, v_{α+1}) = π and consequently v_{α+1} ∉ V_{i+1}. If equality does not hold in (2.5), then from α + 1 + a_{α+1} ≥ i + 1 it follows that v_{i+1} ∈ V_{α+1}, which is equivalent to v_{α+1} ∉ V_{i+1}. Together with V_{1}, …, V_{n} we obtain a vector system V = {v_{1}, …, v_{n}} with cutting vector a. □

Corollary 2.3. Let a = (a_{1}, …, a_{n}) ∈ ℕ^{n} be realizable as cutting vector of a vector system V. Then there exists an index j ∈ {1, …, n} such that

a_{j} ≤ a_{j+1}.

Proof. If we assume that a_{i} = a_{i+1} + 1, i = 1, …, n, then we get the contradiction a_{1} =a_{1} + n. □

Corollary 2.4. Let a = (a_{1}, …, a_{n}) ∈ ℕ^{n} be realizable as cutting vector of a vector system V. If a_{j} ≤ a_{j+1} for some j ∈ {1, …, n}, then

a_{j} ≤ n − 2.  (2.7)

Proof. From (2.2) we know that a_{j} ≤ n − 1. If a_{j+1} < n − 1, then it follows that a_{j} < n − 1. If we assume that a_{j} = a_{j+1} = n − 1, then from (2.4) it follows that

a_{j} = a_{j+1+a_{j+1}} ≤ n − a_{j+1} − 1 = 0,

which is a contradiction. □

Corollary 2.5. Let a = (a_{1}, …, a_{n}) ∈ ℕ^{n} be realizable as cutting vector of a vector system V,

a_{j} ≤ a_{j+1} for some j ∈ {1, …, n} ,

and assume that v_{j} and v_{j+a_{j}+1} are not oppositely directed. Then

a_{j} + a_{j+a_{j}+1} = n − 1 .  (2.8)

Proof. Setting α := a_{j+1} − a_{j}, we get the following observations. From (2.5) we know that

a_{j} + a_{j+a_{j}+1} ≥ n − 1;

on the other hand, from (2.3) it follows that

a_{j+a_{j}+1} = a_{j+a_{j+1}−α+1} ≤ a_{j+1+a_{j+1}} + α,

and from (2.4) we get

a_{j+1+a_{j+1}} + α ≤ n − a_{j+1} − 1 + α = n − a_{j} − 1.

Consequently, (2.8) holds. □

3. Φ_{j}-mappings

Now we deal with the question: How to get a cutting vector from another one?

We will define mappings which correspond to special rotations of the vectors in the vector system. On this way we describe the change of the combinatorial structure of the vector system step by step.

We consider the mapping Φ_{j} : ℕ^{n} ⟶ ℕ^{n}, where

a′ = Φ_{j}(a), j ∈ {1, …, n} is given by

a′_{i} = \{ \begin{matrix}\left\{{a_{i} + 1 for i = j \atop a_{i}  else}\right\} & if a_{j} + a_{j+a_{j}+1} = n − 2 \\ \left\{{a_{i} − 1 for i = j + a_{j} + 1 \atop a_{i}  else}\right\} & if a_{j} + a_{j+a_{j}+1} ≠ n − 2. \end{matrix}  (3.1)

Theorem 3.1. Let k = (k_{1}, …, k_{n}) be the cutting vector of the vector system V. Then k′ = Φ_{j}(k) is realizable as cutting vector of a vector system if the following condition holds:

k_{j} ≤ k_{j+1}.  (3.2)

Proof. Using Corollary 2.4 and Corollary 2.5 it is easy to check that k′ = Φ_{j}(k) fulfils the conditions of Theorem 2.2. □

In the following for given cutting vectors k = (k_{1}, …, k_{n}) and k′ = (k′_{1}, …, k′_{n}) we consider the vector κ = (κ_{1}, …, κ_{n}), where

κ_{i} := k′_{i} − k_{i}, i = 1, …, n.

Corollary 3.2. Let k = (k_{1}, …, k_{n}) and k′ = (k′_{1}, …, k′_{n}) be the cutting vectors of vector systems V and V′, respectively. If κ_{l} > 0 for some l ∈ {1, …, n}, then there exists an index j ∈ {1, …, n} such that

k_{j} ≤ k_{j+1} ∧ κ_{j} > 0.

Proof. If k_{l} ≤ k_{l+1}, then the assertions holds for j = l. If we assume that

k_{i} = k_{i+1} + 1 for i = \{ \begin{matrix}l, …, j − 1 & if & l < j \\ l, …, n + j − 1 & if & l > j \end{matrix} ∧ k_{j} ≤ k_{j+1}

(from Corollary 2.3 we know that such an index j exists), then it follows that

k_{l} = \{ \begin{matrix}k_{j} + (j − l) & if & l < j \\ k_{j} + (n + j − l) & if & l > j. \end{matrix}

On the other hand, from (2.3) it follows that

k′_{l} ≤ \{ \begin{matrix}k′_{j} + (j − l) & if & l < j \\ k′_{j} + (n + j − l) & if & l > j. \end{matrix}

Thus we obtain

κ_{j} = k′_{j} − k_{j} ≥ k′_{l} − k_{l} = κ_{l} > 0.  □

Corollary 3.3. Let k = (k_{1}, …, k_{n}) and k′ = (k′_{1}, …, k′_{n}) be the cutting vectors of vector systems V and V′, respectively. If κ_{j} > 0 for some j ∈ {1, …, n}, then

κ_{j+k_{j}+1} ≤ \{ \begin{matrix}0 & if & k_{j} + k_{j+k_{j}+1} & = n − 2 \\ −1 & if & k_{j} + k_{j+k_{j}+1} & ≥ n − 1. \end{matrix}

Proof.

(1) If k_{j} + k_{j+k_{j}+1} = n − 2, then

k′_{j} + k′_{j+k_{j}+1} = k_{j} + κ_{j} + k_{j+k_{j}+1} + κ_{j+k_{j}+1} = (n − 2) + κ_{j} + κ_{j+k_{j}+1}.

(2) If k_{j} + k_{j+k_{j}+1} ≥ n − 1, then

k′_{j} + k′_{j+k_{j}+1} ≥ (n − 1) + κ_{j} + κ_{j+k_{j}+1}.

(3) Furthermore, from Theorem 2.2 we have

k′_{j} + k′_{j+k_{j}+1} = k′_{j} + k′_{j+k′_{j}−κ_{j}+1} ≤ (n − 1) + (κ_{j} − 1).  □

Corollary 3.4. Let k = (k_{1}, …, k_{n}) and k′ = (k′_{1}, …, k′_{n}) be the cutting vectors of vector systems V and V′, respectively. If κ_{j} < 0 for some j ∈ {1, …, n}, then

κ_{j+k_{j}+1} ≥ \{ \begin{matrix}1 & if & k_{j} + k_{j+k_{j}+1} & = n − 2 \\ 0 & if & k_{j} + k_{j+k_{j}+1} & = n − 1. \end{matrix}

Proof.

(1) If k_{j} + k_{j+k_{j}+1} = n − 2, then

k′_{j} + k′_{j+k_{j}+1} = (n − 2) + κ_{j} + κ_{j+k_{j}+1}.

(2) If k_{j} + k_{j+k_{j}+1} = n − 1, then

k′_{j} + k′_{j+k_{j}+1} = (n − 1) + κ_{j} + κ_{j+k_{j}+1}.

(3) Furthermore, from Theorem 2.2 we have

k′_{j} + k′_{j+k_{j}+1} = k′_{j} + k′_{j+k′_{j}−κ_{j}+1} ≥ (n − 1) + κ_{j} .  □

Corollary 3.5. Let k = (k_{1}, …, k_{n}) and k′ = (k′_{1}, …, k′_{n}) be the cutting vectors of vector systems V and V′, respectively. Then

κ_{j+k_{j}} ≥ \{ \begin{matrix}0 & if & κ_{j} = −1 \\ 1 & if & κ_{j} < −1. \end{matrix}

Proof.

(1) If κ_{j} = −1, then from (2.5) it follows that

k′_{j} + k′_{j+k_{j}} = k′_{j} + k′_{j+k′_{j}−κ_{j}} ≥ n − 2.

(2) If κ_{j} < −1, then from (2.3) and (2.5) it follows that

k′_{j} + k′_{j+k_{j}} = k′_{j} + k′_{j+k′_{j}−κ_{j}} ≥ n − (−κ_{j}).

(3) Furthermore, from (2.4) we have

k′_{j} + k′_{j+k_{j}} = k_{j} + k_{j+k_{j}} + κ_{j} + κ_{j+k_{j}} ≤ (n − 1) + κ_{j} + κ_{j+k_{j}}.  □

From now on we use a further distinction. The vector system V is called non-degenerate if and only if there are no two oppositely directed vectors in V. Otherwise V is said to be degenerate.

Corollary 3.6. Let k = (k_{1}, …, k_{n}) and k′ = (k′_{1}, …, k′_{n}) be the cutting vectors of vector systems V and V′, respectively. If V′ is non-degenerate and

κ_{l} ≤ 0 ∀l ∈ {1, …, n},

then k = k′.

Proof. Assume that κ_{j} < 0 for some j ∈ {1, …, n}.

(1) If κ_{j} < −1, then κ_{j+k_{j}} ≥ 1, by Corollary 3.5, is a contradiction.

(2) If κ_{j} = −1, then κ_{j+k_{j}} ≥ 0 by Corollary 3.5.

(a) If κ_{j+k_{j}} > 0, we have a contradiction.

(b) If κ_{j+k_{j}} = 0, then from (2.4) we get

\begin{aligned}k′_{j} + k′_{j+k′_{j}+1} & = k′_{j} + k′_{j+k_{j}} = k_{j} − 1 + k_{j+k_{j}} \\ & ≤ (n − 1) − 1, \end{aligned}

which is a contradiction. □

In the following we make use of

Φ_{j_{1}}Φ_{j_{2}}(k) := Φ_{j_{1}}(Φ_{j_{2}}(k)) and Ψ_{j}(k) := Φ_{j}Φ_{j}(k).

If k′ = Ψ_{j}(k), then from the definition of Φ_{j} (see (3.1)) it follows that

k′_{i} = \{ \begin{matrix}k_{i} + 1 & for & i = j \\ k_{i} − 1 & for & i = j + k_{j} + 1 \\ k_{i} & else. \end{matrix}

Theorem 3.7. Let k, k′ ∈ ℕ^{n} be realizable as cutting vectors of vector systems V and V′, respectively. Then they may be transformed into each other by a finite number of Φ_{j}-mappings. Each intermediate vector is realizable as cutting vector of a vector system.

Proof. We give an inductive construction:

(1) Setting L := {1, …, n}, κ_{l}^{(0)} := k′_{l} − k_{l}, l = 1, …, n, we consider

L_{+}^{(0)} := {l ∈ L : κ_{l}^{(0)} > 0}.

(2) If L_{+}^{(i)} ≠ ∅, then, according to Corollary 3.2, it follows that there exists j ∈ L_{+}^{(i)} such that k_{j}^{(i)} ≤ k_{j+1}^{(i)} and κ_{j}^{(i)} := k′_{j} − k_{j}^{(i)} > 0.

(a) If k_{j}^{(i)} + k_{j+k_{j}^{(i)}+1}^{(i)} = n − 2, then k^{(i+1)} := Φ_{j}(k^{(i)}) is realizable as cutting vector of

a vector system, and

κ_{l}^{(i+1)} := k′_{l} − k_{l}^{(i+1)} = \{ \begin{matrix}κ_{l}^{(i)} − 1 & if & l = j \\ κ_{l}^{(i)} & else. \end{matrix}

(b) If k_{j}^{(i)} + k_{j+k_{j}^{(i)}+1}^{(i)} = n − 1, then k^{(i+1)} := Ψ_{j}(k^{(i)}) is realizable as cutting vector of

a vector system, and

κ_{l}^{(i+1)} := k′_{l} − k_{l}^{(i+1)} = \{ \begin{matrix}κ_{l}^{(i)} − 1 & if & l = j \\ κ_{l}^{(i)} + 1 & if & l = j + k_{j}^{(i)} + 1 \\ κ_{l}^{(i)} & else. \end{matrix}

From Corollary 3.3 it follows that

κ_{j+k_{j}^{(i)}+1}^{(i+1)} = κ_{j+k_{j}^{(i)}+1}^{(i)} + 1 ≤ 0.

Setting L_{+}^{(i+1)} := {l ∈ L : κ_{l}^{(i+1)} > 0}, in both the cases (a) and (b) we have L_{+}^{(i+1)} ⊆ L_{+}^{(i)}. If L_{+}^{(i+1)} ≠ ∅, the procedure of this part works again.

(3) If L_{+}^{(i)} = ∅ and V′ is non-degenerate, from Corollary 3.6 it follows that k′ = k^{(i)}. Thus, we have to consider only the case where L_{+}^{(i)} = ∅ and V′ is degenerate. If κ_{j}^{(i)} < 0 for some j ∈ L, then by Corollary 3.4 we obtain

κ_{j+k_{j}^{(i)}+1}^{(i)} ≥ \{ \begin{matrix}1 & if & k_{j}^{(i)} + k_{j+k_{j}^{(i)}+1}^{(i)} & = & n − 2 \\ 0 & if & k_{j}^{(i)} + k_{j+k_{j}^{(i)}+1}^{(i)} & = & n − 1. \end{matrix}

G. Heinz: The Concept of Cutting Vectors for Vector Systems… 191

Only the second case is relevant (notice L_{+}^{(i)} = ∅). Thus, we may assume

k_{j}^{(i)} + k_{j+k_{j}^{(i)}+1}^{(i)} = n − 1  (∗_{1})

and

κ_{j+k_{j}^{(i)}+1}^{(i)} := k′_{j+k_{j}^{(i)}+1} − k_{j+k_{j}^{(i)}+1}^{(i)} = 0.  (∗_{2})

Furthermore, from (2.4) we know that

k_{j}^{(i)} + k_{j+k_{j}^{(i)}}^{(i)} ≤ n − 1.  (∗_{3})

(a) If κ_{j}^{(i)} = −1, from (2.5) it follows that

k′_{j} + k′_{j+k_{j}^{(i)}} = k′_{j} + k′_{j+k′_{j}+1} ≥ n − 2.

Thus, together with (∗_{3}) we obtain

κ_{j+k_{j}^{(i)}}^{(i)} = k′_{j+k_{j}^{(i)}} − k_{j+k_{j}^{(i)}}^{(i)} ≥ (n − 2) − k′_{j} + k_{j}^{(i)} − (n − 1) = 0.

Again, only the case κ_{j+k_{j}^{(i)}}^{(i)} = 0 is relevant, and by (∗_{3}) it follows that

k′_{j} + k′_{j+k′_{j}+1} = k_{j}^{(i)} − 1 + k′_{j+k_{j}^{(i)}} = k_{j}^{(i)} + k_{j+k_{j}^{(i)}}^{(i)} − 1 ≤ n − 2.

Together with (2.5) we obtain equality. Consequently,

k_{j}^{(i)} + k_{j+k_{j}^{(i)}}^{(i)} = n − 1.  (∗_{4})

From (∗_{1}) and (∗_{4}) we get

k_{j+k_{j}^{(i)}}^{(i)} = k_{j+k_{j}^{(i)}+1}^{(i)}.

Thus, the conditions of Theorem 3.1 are satisfied and, consequently,

k^{(i+1)} := Φ_{j+k_{j}^{(i)}} (k^{(i)})

is realizable as cutting vector of a vector system. Furthermore, from k_{j+k_{j}^{(i)}}^{(i)} + k_{j+k_{j}^{(i)}+k_{j+k{(i) \atop j}}^{(i)}+1}^{(i)} = k_{j+k_{j}^{(i)}+1}^{(i)} + k_{j}^{(i)} = n − 1

we obtain (see (3.1))

κ_{j}^{(i+1)} = κ_{j}^{(i)} + 1 = 0.

(b) The case κ_{j}^{(i)} < −1 is not relevant, since from Theorem 2.2 it follows that

k′_{j} + k′_{j+k_{j}^{(i)}} = k′_{j} + k′_{j+k′_{j}−κ_{j}^{(i)}} ≥ n + κ_{j}^{(i)}

and, together with (∗_{3}),

κ_{j+k_{j}^{(i)}}^{(i)} = k′_{j+k_{j}^{(i)}} − k_{j+k_{j}^{(i)}}^{(i)} ≥ (n + κ_{j}^{(i)}) − k′_{j} + k_{j}^{(i)} − (n − 1) = 1.

If κ_{j}^{(i+1)} < 0 for some j ∈ L, then the procedure of this part works again.

(4) The procedure of part (2) and (3) stops at i = ĩ if κ ˜(i) ; l = 0, l = 1, …, n. □

Example 3.8. We consider

\begin{aligned}k & = & (5, 6, 5, 5, 5, 4, 3, 3, 4, 4) \\ k′ & = & (7, 6, 5, 5, 4, 3, 2, 1, 4, 7). \end{aligned}

The vectors k and k′ satisfy the conditions of Theorem 2.2. We obtain

\begin{aligned}k^{(1)} & = & Φ_{1}(k) & = & (6, 6, 5, 5, 5, 4, 3, 3, 4, 4) \\ k^{(2)} & = & Ψ_{1}(k^{(1)}) & = & (7, 6, 5, 5, 5, 4, 3, 2, 4, 4) \\ k^{(3)} & = & Ψ_{10}(k^{(2)}) & = & (7, 6, 5, 5, 4, 4, 3, 2, 4, 5) \\ k^{(4)} & = & Ψ_{10}(k^{(3)}) & = & (7, 6, 5, 5, 4, 3, 3, 2, 4, 6) \\ k^{(5)} & = & Ψ_{10}(k^{(4)}) & = & (7, 6, 5, 5, 4, 3, 2, 2, 4, 7) \\ k′ & = & Φ_{10}(k^{(5)}) & = & (7, 6, 5, 5, 4, 3, 2, 1, 4, 7). \end{aligned}

Thus k′ = Φ(k) holds, where Φ := Φ_{10}Ψ_{10}Ψ_{10}Ψ_{10}Ψ_{1}Φ_{1}.

References

[1] Björner, A.; Las Vergnas, M.; Sturmfels, B.; White, N.; Ziegler, G.: Oriented Matroids. Cambridge University Press 1993.

[2] Bland, R.; Las Vergnas, M.: Orientability of matroids. J. Combin. Theory Ser. B 24 (1978), 94–123.

[3] Bokowksi, J.: Oriented Matroids. In: Handbook on Convex Geometry (eds. P. Gruber, J. Wills), North-Holland, Amsterdam 1993, 555–602.

[4] Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer Verlag, Berlin 1987.

[5] Folkman, J.; Lawrence, J.: Oriented Matroids. J. Combin. Theory Ser. B 25 (1978), 199–236.

[6] Grünbaum, B.: Convex Polytopes. Wiley, London 1967.

[7] Heinz, G.: The total weight of the cells of semi-rich, acyclic arrangements of oriented lines in the plane. Preprint.

[8] Karlander, J.: A characterization of affine sign vector systems. To appear in: European Journal of Combinatorics.

[9] Linhart, J.: On the total weight of arrangements of halfplanes. Geom. Dedicata 43 (1993), 165–172.

[10] Linhart, J.: Arrangements of oriented hyperplanes. Discrete Comput. Geom. 10 (1993), 435–446.

Received Oktober 19, 1998; revised version March 24, 1999