DIRECTION-CRITICAL CONFIGURATIONS IN NONCENTRAL GENERAL POSITION SILVIA FERNÁNDEZ-MERCHANT AND RIMMA HÄMÄLÄINEN

2025-05-03 0 0 573.41KB 20 页 10玖币

侵权投诉

DIRECTION-CRITICAL CONFIGURATIONS IN NONCENTRAL

GENERAL POSITION

SILVIA FERNÁNDEZ-MERCHANT AND RIMMA HÄMÄLÄINEN

Abstract. In 1982, Ungar proved that the connecting lines of a set of nnon-

collinear points in the plane determine at least 2bn/2cdirections (slopes). Sets

achieving this minimum for nodd (even) are called direction-(near)-critical

and their full classiﬁcation is still open. To date, there are four known inﬁ-

nite families and over 100 sporadic critical conﬁgurations. Jamison conjectured

that any direction-critical conﬁguration with at least 50 points belongs to those

four inﬁnite families. Interestingly, except for a handful of sporadic conﬁgu-

rations, all these conﬁgurations are centrally symmetric. We prove Jamison’s

conjecture, and extend it to the near-critical case, for centrally symmetric

conﬁgurations in noncentral general position, where only the connecting lines

through the center of symmetry may pass through more than two points. As

in Ungar’s proof, our results are proved in the more general setting of allow-

able sequences. We show that, up to equivalence, the central signature of a set

uniquely determines a centrally symmetric direction-(near)-critical allowable

sequence in noncentral general position, and classify such allowable sequences

that are geometrically realizable.

1. Introduction

In 1970, Scott [9] proposed the problem of ﬁnding the least number of directions

(slopes) determined by a set of npoints in the plane, not all collinear. He conjec-

tured that the minimum number of diﬀerent slopes determined by the connecting

lines of a set of nnoncollinear points in the plane is 2bn/2c. This conjecture was

completely settled by Ungar in 1982 [10]. Sets with npoints and n−1directions are

called direction-critical (or slope-critical); and sets with npoints and ndirections

are called direction-near-critical. Hence, the sets achieving the minimum in Un-

gar’s Theorem are the direction-critical conﬁgurations, which always have an odd

number of points and so we call them odd-critical; and the direction near-critical

conﬁgurations with an even number of points, which we call even-near-critical.

After Ungar’s result, the focus naturally switched to the classiﬁcation of direction

(near)-critical conﬁgurations. In 1983, Jamison and Hill [5] described four inﬁnite

families and over a hundred sporadic odd-critical conﬁgurations (details in Section

4). They noted that the four inﬁnite families and all but four sporadic conﬁgurations

are centrally symmetric. Jamison conjectured that any odd-critical conﬁguration

with at least 50 points belongs to those four families [7]. He also proved that any

near-critical set of points in general position is an aﬃne copy of the vertices of a

regular polygon[7, 6]. In his analysis, Jamison deﬁnes a dividing line of a set of

points Pas a line connecting points of Pthat divides the rest of Pin half. These

lines are best known as halving lines of P. The cyclic sequence of positive integers

corresponding to half the number of points per halving line of Pminus its center,

read in counterclockwise order, is the central signature of P.

arXiv:2210.12465v1 [math.CO] 22 Oct 2022

2 SILVIA FERNÁNDEZ-MERCHANT AND RIMMA HÄMÄLÄINEN

Inspired by this work, we study centrally symmetric conﬁgurations. We extend

the notion of general position to sets in non-central general position, where the only

lines possibly passing through more than two points of the set are its halving lines.

We completely classify the centrally symmetric conﬁgurations in noncentral general

position that achieve the minimum in Ungar’s Theorem. More precisely, in Theorem

4.3, we prove that all but one centrally symmetric odd-critical conﬁguration of

points in noncentral general position belongs to one of the 4 families described in

Jamison’s Conjecture. All even-near-critical conﬁgurations are obtained from the

odd-critical by removing their center of symmetry.

Moreover, as in Ungar’s Theorem, our analysis extends to the setting of allowable

sequences [2, 3] (deﬁnition and more details is Section 2). Goodman and Pollack

[4] showed that any allowable sequence corresponds to a generalized conﬁguration

of points, that is, a set of points together with a pseudoline arrangement so that

every pair of points is contained in a unique pseudoline. Note that the set of con-

ﬁgurations of points is then a proper subset of the set of generalized conﬁgurations

of points/allowable sequences. In contrast to our geometric classiﬁcation, we prove

in Theorem 3.4 that, up to combinatorial equivalence, any cyclic sequence of posi-

tive integers is the central signature of a unique even-near-critical and (by adding

the center of symmetry) a unique odd-critical centrally symmetric allowable se-

quence in noncentral general position. Only a few of these allowable sequences are

geometrically realizable, as shown by Theorem 4.3.

The paper is organized as follows. In Section 2, we present the deﬁnition of

allowable sequence, related notation and results. In Section 3, we determine the

structure of any even-near-critical centrally symmetric allowable sequence in non-

central general position in terms of its central signature, Theorem 3.1 and Corollary

3.2; and show their existence in Theorem 3.3. In Section 4, we describe some known

results about the classiﬁcation of odd-critical and even-near critical geometric con-

ﬁgurations and state Theorem 4.3, which fully determines the even-near critical,

and thus the odd-critical, allowable sequences from Theorem 3.4 that are geomet-

rically realizable. The proof of this result follows from Theorems 4.7-4.10, that we

present in Section 4.4.

2. Allowable sequences

Let Pbe a set of npoints in the plane. The circular sequence Π(P)associated

with Pis a doubly-inﬁnite sequence of permutations of the points in Pdetermined

by the projections of Ponto a line that rotates around a circle enclosing P. As

an abtract generalization of a circular sequence, an allowable sequence of npoints

is a doubly-inﬁnite periodic sequence of permutations Π = {πi}∞

i=−∞ of the set of

points [n] := {1,2,3, . . . , n}, satisfying the following properties:

(1) By relabeling the points, it can be assumed that π0= (1,2,3, . . . , n).

(2) There is h∈Z+such that πi+his the reversal of πifor every i∈Z. Then Π

has period 2hand {π0, π1, . . . , πh}is a halfperiod of Πof length h=h(Π).

(3) πiis obtained from πi−1by the reversal of one or more disjoint substrings,

each involving consecutive elements of πi−1. These reversals are called

switches, and the set of switches occuring from πi−1to πiis the ith move

of Π.

(4) Any pair of points participates in a switch exactly once within a halfperiod.

DIRECTION-CRITICAL CONFIGURATIONS IN NONCENTRAL GENERAL POSITION 3

If Πis an allowable sequence on the set of points [n]and S ⊆ [n], then the

allowable sequence induced by S, denoted by Π|S, is obtained from Πby deleting

the points not in Sfrom each permutation and removing repeated permutations.

Allowable sequences were used by Goodman and Pollack to approach combina-

torial problems of sets of points in the 1980s [2, 3]. Since circular sequences are

especial cases of allowable sequeces, every set of points corresponds to an allow-

able sequence but not every allowable sequence is the circular sequence of a set of

points. In fact, Goodman and Pollack [4] showed that up to combinatorial equiva-

lence, there is a one-to-one correspondence between the set of allowable sequences

and the set of generalized conﬁgurations of points. In this new setting, all switches

occurring between consecutive permutations of an allowable sequence correspond

to pseudolines determining the same direction. That is, the number of directions

determined by an allowable sequence Πis the length h(Π) of its halfperiod. Ungar

proved that if Πis an allowable sequence with npoints, then h(Π) ≥2bn/2c. In

other words, the odd-critical and even-near-critical allowable sequences are those

with npoints and half-period of length 2bn/2c.

Since odd centrally symmetric conﬁgurations are precisely those obtained from

even ones by adding their center of symmetry, we only consider even conﬁgurations.

All relevant concepts are naturally extended to allowable sequences. Let Πbe an

allowable sequence of 2npoints. For a permutation πand a point pof Π, the position

of pin πis denoted by π(p).Πis centrally symmetric if for every point pthere is a

point psuch that π(p)+π(p)=2n+1 for any permutation π∈Π. The points pand

pare centrally symmetric and they are said to be conjugates. So pis the conjugate

of p, and p=pis the conjugate of p. The switches reversing a centered substring

of a permutation are called crossing switches. They correspond to the halving lines

of a set of points and they all pass through the center of symmetry of the set.

The sequence (d1, d2, . . . , dt), where 2diis the number of points reversed by the ith

crossing switch in the halfperiod π0, π1...,πhof Π, is the central signature of Π

and tis its central degree. Allowable sequences all whose switches are transpositions

(switches of two points) are said to be in general position. Allowable sequences in

which all switches, except perhaps for the crossing switches, are transpositions are

said to be in noncentral general position. (The central signature of an allowable

sequence is also called a crossing distance partition [1]).

We consider the following questions: Which cyclic positive integer sequences are

the central signature of an odd-critical or even-near-critical centrally symmetric al-

lowable sequence in noncentral general position? Which of such allowable sequences

are geometrically realizable, that is, they are the circular sequence of a set of points?

In the rest of the paper, Π = {πi}i∈Zis an even-near-critical centrally symmetric

allowable sequence with 2npoints in noncentral general position and with central

signature (d1, d2, . . . , dt)for some t≥2. We assume that π0= (1,2, . . . , n −

1, n, n, n −1,...,2,1) and that the ﬁrst crossing switch occurs in the ﬁrst move

(from π0to π1). The ith crossing switch in the halfperiod starting at π0reveres

a centered substring siof 2dipoints, which we call a crossing substring. Before

reversing,

si= (si(1), si(2), . . . , si(di), si(di+ 1), si(di+ 2), . . . , si(2di))

= (si(1), si(2), . . . , si(di), si(di), si(di−1), . . . , si(2di)).

4 SILVIA FERNÁNDEZ-MERCHANT AND RIMMA HÄMÄLÄINEN

Figure 1 shows an example of a halfperiod of an even-near-critical centrally

symmetric allowable sequence in noncentral general position with 2n= 12 points

and central signature (3,2,1). Its reversed crossing substrings are highlighted to

easily identify the crossing switches. This sequence is not geometrically realizable.

{πi}12

i=0 =







1 2 3 4 5 6 6 5 4 3 2 1

1 3 2 4 5 6 6 5 4 2 3 1

3 1 4 2 5 6 6 5 2 4 1 3

3 4 1 5 2 6 6 2 5 1 4 3

4 3 5 1 6 2 2 6 1 5 3 4

4 5 3 6 1 2 2 1 6 3 5 4

4 5 6 3 1 2 2 1 3 6 5 4

4 5 6 1 3 2 2 3 1 6 5 4

4 5 1 6 2 3 3 2 6 1 5 4

4 1 5 2 6 3 3 6 2 5 1 4

1 4 2 5 3 6 6 3 5 2 4 1

1 2 4 3 5 6 6 5 3 4 2 1

1 2 3 4 5 6 6 5 4 3 2 1







Figure 1. An even-near-critical centrally symmetric allowable in

noncentral general position and sequence with central signature

(3,2,1).

3. Direction-critical allowable sequences

As a consequence of Ungar’s proof [10], a centrally symmetric allowable sequence

Πis even-near-critical if and only if between the ith and (i+ 1)th crossing switches,

there are exactly di+di+1 −1permutations. In this case, n=d1+d2+··· +dt.

In order to understand the structure of the allowable sequences at hand, we

deﬁne the path of the point pin Π, denoted by γ(p), as a sequence of letters c,p,

rand lof length 2nthat tracks the movement of pthrough the halfperiod of Π

starting at π0. More precisely, the ith entry of γ(p)is

•cif pparticipates in a crossing switch from πi−1to πi, this is a central

jump;

•pif pdoes not participate in any switch from πi−1to πi, this is a passive

jump;

•rif the position of pin πiis to the right of that in πi−1, this is a right

jump;

•lif the position of pin πiis to the left of that πi−1, this is a left jump.

Similar notation was used by Jamison [6]. Now we are ready to state our ﬁrst result.

Theorem 3.1. Let Πbe an even-near-critical centrally symmetric allowable se-

quence of npoints in noncentral general position equipped with the central signature

(d1, d2...,dt). If the ﬁrst move contains a crossing switch, then for 1≤k≤d1,

γ(s1(k)) = c p ···p

|{z }

k−1

r···r

| {z }

n−d1

p···p

|{z }

2(d1−k)+1

l···l

|{z}

n−d1

p···p

|{z }

k−1

,and so

γ(s1(k)) = c p ···p

|{z }

k−1

l···l

|{z}

n−d1

p···p

|{z }

2(d1−k)+1

r···r

| {z }

n−d1

p···p

|{z }

k−1

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

DIRECTION-CRITICALCONFIGURATIONSINNONCENTRALGENERALPOSITIONSILVIAFERNÁNDEZ-MERCHANTANDRIMMAHÄMÄLÄINENAbstract.In1982,Ungarprovedthattheconnectinglinesofasetofnnon-collinearpointsintheplanedetermineatleast2bn=2cdirections(slopes).Setsachievingthisminimumfornodd(even)arecalleddirection-(near)-critical...

展开>> 收起<<

DIRECTION-CRITICAL CONFIGURATIONS IN NONCENTRAL GENERAL POSITION SILVIA FERNÁNDEZ-MERCHANT AND RIMMA HÄMÄLÄINEN.pdf

共20页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

DIRECTION-CRITICAL CONFIGURATIONS IN NONCENTRAL GENERAL POSITION SILVIA FERNÁNDEZ-MERCHANT AND RIMMA HÄMÄLÄINEN

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: