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

Institute of Software Technology, Graz University of Technology, Graz, Austria,

daperz@ist.tugraz.at, bvogt@ist.tugraz.at

Abstract

Let

be a set of

points in general position in the plane. The Second

Selection Lemma states that for any family of Θ(

) triangles spanned by

, 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

is a triangle spanned by

not containing any point of

in its interior.

B´ar´any conjectured that there exist an edge spanned by

that is incident

to a super constant number of empty triangles of

. The number of empty

triangles of

might be

(

); in such a case, on average, every edge

spanned by

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.

Speciﬁcally, we show that for any integer

and real number 0

≤α≤

there exists a point set of size

with Θ(

n3−α

) empty triangles such that

any point of the plane is only in O(n3−2α) empty triangles.

1 Introduction

Let

be a set of

points in general position

in the plane. A triangle of

is a

triangle whose vertices are points of

. We say that a point

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.

A point set

S⊂Rd

is in general position if for every integer 1

< k ≤d

+ 1, no subset of

points of Sis contained in a (k−2)-dimensional ﬂat.

arXiv:2210.00630v1 [cs.CG] 2 Oct 2022

triangle ∆ if it lies in the interior of ∆. Boros and F¨uredi [

] showed that for any

point set

in general position in the plane, there exists a point in the plane which

stabs a constant fraction (

(

)) of the triangles of

. B´ar´any [

] extended

the result to

; he showed that there exists a constant

cd>

0, depending only

, such that for any point set

Sd⊂Rd

in general position, there exists a point

which is in the interior of

cdnd+1 d

-dimensional simplices spanned by

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,

, of triangles of

. B´ar´any, F¨uredi and Lov´asz [

]

showed that for any point set

in the plane in general position and any family

of Θ(

) triangles of

, there exists a point of the plane which stabs Θ(

)

triangles from

. This result, generalized to

by Alon et al. [

], is now also

known as Second Selection Lemma [13].

Both results for the plane require families of Θ(

) triangles of

. It is

natural to ask about families of triangles of smaller cardinality. For this question,

Aronov et al. [

] showed that for every 0

≤α≤

1 and every family

of Θ(

n3−α

)

triangles of

, there exists a point of the plane which stabs Ω(

n3−3α/log5n

)

triangles of

. This lower bound was improved by Eppstein [

] to the maximum

n3−α/

n−

5) and Ω(

n3−3α/log2n

). A mistake in one of the proofs was

later found and ﬁxed by Nivasch and Sharir [

]. Furthermore, Eppstein [

]

constructed

-point sets and families of

n3−α

triangles in them such that every

point of the plane is in at most

n3−α/

n−

5) triangles for

α≥

1 and in at most

n3−2α

triangles for 0

≤α≤

1. Hence, for the number of triangles of a family

that can be guaranteed to simultaneously contain some point of the plane, there

is a continuous transition from a linear fraction for

|F|

(

) to a constant

fraction for |F| = Θ(n3).

A triangle of

is said to be empty if it does not contain any points of

its interior. Let τ(S) be the number of empty triangles of S. It is easily shown

that

(

) is Ω(

); Katchalski and Meir [

] showed that there exist

-point sets

with

(

) = Θ(

). Note that for such point sets, an edge of

is on average

part of a constant number of empty triangles of

. However, B´ar´any conjectured

that there is always an edge of

which is part of a super constant number of

empty triangles of

; see [

]. B´ar´any et al. [

] proved this conjecture for

random

-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

, for any set

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

. 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. Speciﬁcally, we prove the following.

Theorem 1

For every integer

and every 0

≤α≤

1, there exist sets

points with

(

) = Θ

(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 [

] constructed a family of arbitrary large sets without

large empty convex polygons. Valtr [

] generalized Horton’s construction and

named the resulting sets “Horton sets”. Squared Horton sets were deﬁned by

Valtr [

] (as set

in Section 4). B´ar´any and Valtr [

] 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 deﬁnition 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

be a set of

points in the plane such that no two points have the same

-coordinate. In the following, we consider the points of

in increasing order

of their x-coordinates. We denote with X0the subset of Xthat contains every

second point of

(w.r.t. the

-order of the points), starting with the leftmost

point of

. Similarly,

X\X0

is the subset of

that contains every

second point of

(and does not contain the leftmost point of

). In other

words, if the points of

are labeled

{p0, p1, . . . , pn−1}

in increasing

-order,

then

{p0, p2,...,}

and

{p1, p3, . . . }

. In general, for a binary string

, we denote as

the subset of vertices of

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

and

in the plane such that no two points

X∪Y

have the same

-coordinate. We say that

is high above

if every

line passing through two points of

is above every point of

, and

is deep

below

if every line passing through two points of

is below every point of

Using the above notation, we can now deﬁne Horton sets.

Deﬁnition 1

Let

be a set of

points in general position in the plane, such

that no two points of

have the same

-coordinate. Then

is a

Horton set

1. |H| ≤ 2; or

2. |H|>

and

are Horton sets, and

is high above

and

deep below H1.

One classic way to obtain a Horton

set with 2

points is by starting

with a set

of two points on a horizontal line, and then iteratively duplicating

it by adding a translated copy

, where

is translated to the right by

exactly half the

-distance between the ﬁrst two points of

and the translation

-direction is such that

lies high above

. 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 deﬁnition.

Observation 1

Let

{p0, . . . , pn−1}

be a Horton set with points labeled in

increasing

-order. Then for any 0

≤i≤j≤n−

1, the subset

{pi, pi+1, . . . , pj}

of consecutive points in

-direction again forms a Horton set. Similarly, for any

integer

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 deﬁnition. 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 deﬁne visible

edges in Horton sets. Let

H0∪H1

be a Horton set of at least 4 points.

We say that an edge

= (

pi, pj

), with

pi, pj∈H0

, is visible from above if

below the line spanned by

and

for every

pk∈H0

with

i<k<j

. Likewise,

an edge

= (

pi, pj

), with

pi, pj∈H1

, is visible from below if

is above the line

spanned by

and

for every

pk∈H1

with

i<k<j

. An edge of

is visible

if it is either visible from above or visible from below.

Lemma 2

An edge

spanned by two vertices of a Horton set

is visible from

below (above) if and only if it is spanned by two consecutive vertices of

where

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 ﬁrst direction of the proof, let (

pi, pj

) be an edge of

that visible

from below. Then, by the deﬁnition of visibility,

pi, pj∈H1

. Let

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 ﬁrst that

is of the form

for some binary strings

Let

be the point of

Hb1

that lies between

and

. Note that

pk∈Hb10

By the deﬁnition of Horton sets

is below the line spanned by

and

; this

contradicts the assumption that (

pi, pj

) is visible from below. Thus,

is a binary

string that only consists of 0s.

Next, suppose that

and

are not consecutive vertices of

H1b0

. Then

there exists a point

pk∈H1b00⊂H1

that lies between

and

. Again, by

the deﬁnition of Horton sets,

is below the line spanned by

and

, which

contradicts the assumption that (

pi, pj

) is visible from below. Hence, for

= 1

and

are consecutive vertices in

. The reasoning for an edge (

pi, pj

) that

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

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

10 玖币 0人已下载

立即下载

摘要：

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

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

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: