No Selection Lemma for Empty Triangles Ruy Fabila-Monroy1Carlos Hidalgo-Toscano1 Daniel Perz2Birgit Vogtenhuber2

2025-05-02 0 0 500.87KB 17 页 10玖币
侵权投诉
No Selection Lemma for Empty Triangles
Ruy Fabila-Monroy1Carlos Hidalgo-Toscano1
Daniel Perz2Birgit Vogtenhuber2
1Departamento de Matem´aticas, Cinvestav, Ciudad de M´exico, M´exico,
ruyfabila@math.cinvestav.edu.mx, cmhidalgo@math.cinvestav.mx
2
Institute of Software Technology, Graz University of Technology, Graz, Austria,
daperz@ist.tugraz.at, bvogt@ist.tugraz.at
Abstract
Let
S
be a set of
n
points in general position in the plane. The Second
Selection Lemma states that for any family of Θ(
n3
) triangles spanned by
S
, there exists a point of the plane that lies in a constant fraction of them.
For families of Θ(
n3−α
) triangles, with 0
≤α≤
1, there might not be a
point in more than Θ(
n3−2α
) of those triangles. An empty triangle of
S
is a triangle spanned by
S
not containing any point of
S
in its interior.
B´ar´any conjectured that there exist an edge spanned by
S
that is incident
to a super constant number of empty triangles of
S
. The number of empty
triangles of
S
might be
O
(
n2
); in such a case, on average, every edge
spanned by
S
is incident to a constant number of empty triangles. The
conjecture of B´ar´any suggests that for the class of empty triangles the
above upper bound might not hold. In this paper we show that, somewhat
surprisingly, the above upper bound does in fact hold for empty triangles.
Specifically, we show that for any integer
n
and real number 0
≤α≤
1
there exists a point set of size
n
with Θ(
n3−α
) empty triangles such that
any point of the plane is only in O(n3−2α) empty triangles.
1 Introduction
Let
S
be a set of
n
points in general position
1
in the plane. A triangle of
S
is a
triangle whose vertices are points of
S
. We say that a point
p
of the plane stabs a
This project has received funding from the European Union’s Horizon 2020
research and innovation programme under the Marie Sk lodowska-Curie grant
agreement No 734922.
D.P. and B.V. were partially supported by the Austrian Science Fund within the collaborative
DACH project Arrangements and Drawings as FWF project I 3340-N35.
1
A point set
S⊂Rd
is in general position if for every integer 1
< k ≤d
+ 1, no subset of
k
points of Sis contained in a (k−2)-dimensional flat.
1
arXiv:2210.00630v1 [cs.CG] 2 Oct 2022
triangle ∆ if it lies in the interior of ∆. Boros and F¨uredi [
8
] showed that for any
point set
S
in general position in the plane, there exists a point in the plane which
stabs a constant fraction (
n3
27
+
O
(
n2
)) of the triangles of
S
. B´ar´any [
3
] extended
the result to
Rd
; he showed that there exists a constant
cd>
0, depending only
on
d
, such that for any point set
Sd⊂Rd
in general position, there exists a point
in
Rd
which is in the interior of
cdnd+1 d
-dimensional simplices spanned by
Sd
.
This result is known as First Selection Lemma [13].
Later, researchers considered the problem of the existence of a point in many
triangles of a given family,
F
, of triangles of
S
. B´ar´any, F¨uredi and Lov´asz [
4
]
showed that for any point set
S
in the plane in general position and any family
F
of Θ(
n3
) triangles of
S
, there exists a point of the plane which stabs Θ(
n3
)
triangles from
F
. This result, generalized to
Rd
by Alon et al. [
1
], is now also
known as Second Selection Lemma [13].
Both results for the plane require families of Θ(
n3
) triangles of
S
. It is
natural to ask about families of triangles of smaller cardinality. For this question,
Aronov et al. [
2
] showed that for every 0
≤α≤
1 and every family
F
of Θ(
n3−α
)
triangles of
S
, there exists a point of the plane which stabs Ω(
n3−3α/log5n
)
triangles of
F
. This lower bound was improved by Eppstein [
9
] to the maximum
of
n3−α/
(2
n−
5) and Ω(
n3−3α/log2n
). A mistake in one of the proofs was
later found and fixed by Nivasch and Sharir [
14
]. Furthermore, Eppstein [
9
]
constructed
n
-point sets and families of
n3−α
triangles in them such that every
point of the plane is in at most
n3−α/
(2
n−
5) triangles for
α≥
1 and in at most
n3−2α
triangles for 0
≤α≤
1. Hence, for the number of triangles of a family
F
that can be guaranteed to simultaneously contain some point of the plane, there
is a continuous transition from a linear fraction for
|F|
=
O
(
n2
) to a constant
fraction for |F| = Θ(n3).
A triangle of
S
is said to be empty if it does not contain any points of
S
in
its interior. Let τ(S) be the number of empty triangles of S. It is easily shown
that
τ
(
S
) is Ω(
n2
); Katchalski and Meir [
12
] showed that there exist
n
-point sets
S
with
τ
(
S
) = Θ(
n2
). Note that for such point sets, an edge of
S
is on average
part of a constant number of empty triangles of
S
. However, B´ar´any conjectured
that there is always an edge of
S
which is part of a super constant number of
empty triangles of
S
; see [
10
,
5
]. B´ar´any et al. [
6
] proved this conjecture for
random
n
-point sets, showing that for such such sets, Θ(
n/ log n
) empty triangles
are expected to share an edge. Note that the expected total number of empty
triangles in such point sets is Θ(n2); see [16].
B´ar´any’s conjecture suggests that perhaps there is always a point of the
plane stabbing many empty triangles of
S
, for any set
S
of
n
points in general
position. Naturally, the mentioned lower bounds for the number of triangles
stabbed by a point of the plane also apply for the family of all empty triangles
of
S
. In contrast, the upper bound constructions of Eppstein do not apply, since
they contain non-empty triangles or do not contain all empty triangles of their
underlying point sets. In this paper, we show that the existence of a point in
more triangles than these upper bounds for general families of triangles is not
guaranteed; hence the title of our paper. Specifically, we prove the following.
2
Theorem 1
For every integer
n
and every 0
≤α≤
1, there exist sets
S
of
n
points with
τ
(
S
) = Θ
(n3−α)
empty triangles where every point of the plane
stabs O(n3−2α)empty triangles of S.
To prove Theorem 1 for
α
= 1, we utilize the so called Horton sets and squared
Horton sets. Horton [
11
] constructed a family of arbitrary large sets without
large empty convex polygons. Valtr [
15
] generalized Horton’s construction and
named the resulting sets “Horton sets”. Squared Horton sets were defined by
Valtr [
15
] (as set
Ak
in Section 4). B´ar´any and Valtr [
7
] showed that squared
Horton sets of size nspan only Θ(n2) empty triangles.
Outline.
The remainder of this paper is organized as follows: In Section 2,
we give the definition of Horton sets and show several properties of them that
will be of use for later sections. Section 3 considers squared Horton sets and
contains a proof of Theorem 1 for the case
α
= 1 (Theorem 11). And in Section 4
we present a generalized construction based on squared Horton sets, which we
analyze to prove Theorem 1.
2 Horton sets
Let
X
be a set of
n
points in the plane such that no two points have the same
x
-coordinate. In the following, we consider the points of
X
in increasing order
of their x-coordinates. We denote with X0the subset of Xthat contains every
second point of
X
(w.r.t. the
x
-order of the points), starting with the leftmost
point of
X
. Similarly,
X1
=
X\X0
is the subset of
X
that contains every
second point of
X
(and does not contain the leftmost point of
X
). In other
words, if the points of
X
are labeled
{p0, p1, . . . , pn−1}
in increasing
x
-order,
then
X0
=
{p0, p2,...,}
and
X1
=
{p1, p3, . . . }
. In general, for a binary string
b
, we denote as
Xb
the subset of vertices of
X
that is obtained by recursively
applying the above splitting. For example,
X10
consists of every second point of
X1and does not contain the leftmost point of X1.
Now consider two point sets
X
and
Y
in the plane such that no two points
of
X∪Y
have the same
x
-coordinate. We say that
Y
is high above
X
if every
line passing through two points of
Y
is above every point of
X
, and
X
is deep
below
Y
if every line passing through two points of
X
is below every point of
Y
.
Using the above notation, we can now define Horton sets.
Definition 1
Let
H
be a set of
n
points in general position in the plane, such
that no two points of
H
have the same
x
-coordinate. Then
H
is a
Horton set
if
1. |H| ≤ 2; or
2. |H|>
2,
H0
and
H1
are Horton sets, and
H1
is high above
H0
and
H0
is
deep below H1.
3
One classic way to obtain a Horton
H
=
Sk
set with 2
k
points is by starting
with a set
S1
of two points on a horizontal line, and then iteratively duplicating
it by adding a translated copy
S0
i
of
Si
, where
S0
i
is translated to the right by
exactly half the
x
-distance between the first two points of
Si
and the translation
in
y
-direction is such that
S0
i
lies high above
Si
. In the resulting Horton set, all
points are evenly spaced in x-direction.
The following observation states that Horton sets have nice subset properties.
They are directly implied by their definition.
Observation 1
Let
H
=
{p0, . . . , pn−1}
be a Horton set with points labeled in
increasing
x
-order. Then for any 0
≤i≤j≤n−
1, the subset
{pi, pi+1, . . . , pj}
of consecutive points in
x
-direction again forms a Horton set. Similarly, for any
integer
k
and 0
≤i≤kj ≤n−
1, the set
{pi, pi+k, pi+2k, . . . , pi+jk}
is again a
Horton set.
We remark that a linear transformation of a Horton set, like for example a
rotation, might no longer be a Horton set by the above definition. However, the
combinatorial properties of these sets do not change. Hence, for convenience, we
still call them Horton sets.
To analyze properties of the empty triangles of Horton sets, we define visible
edges in Horton sets. Let
H
=
H0∪H1
be a Horton set of at least 4 points.
We say that an edge
e
= (
pi, pj
), with
pi, pj∈H0
, is visible from above if
pk
is
below the line spanned by
pi
and
pj
for every
pk∈H0
with
i<k<j
. Likewise,
an edge
e
= (
pi, pj
), with
pi, pj∈H1
, is visible from below if
pk
is above the line
spanned by
pi
and
pj
for every
pk∈H1
with
i<k<j
. An edge of
H
is visible
if it is either visible from above or visible from below.
Lemma 2
An edge
e
spanned by two vertices of a Horton set
H
is visible from
below (above) if and only if it is spanned by two consecutive vertices of
Hb
,
where
b
is a binary string consisting of a single 1followed by an arbitrary number
of 0s (a single 0followed by an arbitrary number of 1s).
Proof.
For the first direction of the proof, let (
pi, pj
) be an edge of
H
that visible
from below. Then, by the definition of visibility,
pi, pj∈H1
. Let
b0
be the
unique binary string such that
pi, pj∈H1b0
and such that either
pi∈H1b00
and
pj∈H1b01
, or
pi∈H1b00
and
pj∈H1b01
. Without loss of generality assume that
pi∈H1b00and pj∈H1b01.
Suppose first that
b0
is of the form
b0
=
b1
1
b2
for some binary strings
b1
,
b2
.
Let
pk
be the point of
Hb1
that lies between
pi
and
pj
. Note that
pk∈Hb10
.
By the definition of Horton sets
pk
is below the line spanned by
pi
and
pj
; this
contradicts the assumption that (
pi, pj
) is visible from below. Thus,
b0
is a binary
string that only consists of 0s.
Next, suppose that
pi
and
pj
are not consecutive vertices of
H1b0
. Then
there exists a point
pk∈H1b00⊂H1
that lies between
pi
and
pj
. Again, by
the definition of Horton sets,
pk
is below the line spanned by
pi
and
pj
, which
contradicts the assumption that (
pi, pj
) is visible from below. Hence, for
b
= 1
b0
,
pi
and
pj
are consecutive vertices in
Hb
. The reasoning for an edge (
pi, pj
) that
4
摘要：

NoSelectionLemmaforEmptyTrianglesRuyFabila-Monroy1CarlosHidalgo-Toscano1DanielPerz2BirgitVogtenhuber21DepartamentodeMatematicas,Cinvestav,CiudaddeMexico,Mexico,ruyfabila@math.cinvestav.edu.mx,cmhidalgo@math.cinvestav.mx2InstituteofSoftwareTechnology,GrazUniversityofTechnology,Graz,Austria,daperz@...

展开>> 收起<<
No Selection Lemma for Empty Triangles Ruy Fabila-Monroy1Carlos Hidalgo-Toscano1 Daniel Perz2Birgit Vogtenhuber2.pdf

共17页,预览4页

还剩页未读， 继续阅读

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

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：17 页 大小：500.87KB 格式：PDF 时间：2025-05-02

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 17
评分 收藏
分享
立即下载
客服
关注