Blocking Delaunay Triangulations from the Exterior Oswin Aichholzer1Thomas Hackl1Maarten L oer2Alexander Pilz1 Irene Parada3Manfred Scheucher4Birgit Vogtenhuber1

2025-05-06 0 0 708.7KB 10 页 10玖币

侵权投诉

Blocking Delaunay Triangulations from the Exterior∗

Oswin Aichholzer1Thomas Hackl1Maarten L¨oﬄer2Alexander Pilz1

Irene Parada3Manfred Scheucher4Birgit Vogtenhuber1

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

oaich@ist.tugraz.at,bvogt@ist.tugraz.at

2Department of Information and Computing Sciences,

Utrecht University, Netherlands,

m.loffler@uu.nl

3Department of Applied Mathematics and Computer Science,

Technical University of Denmark

irmde@dtu.dk

4Institut f¨ur Mathematik, Technische Universit¨at Berlin, Germany

lastname@math.tu-berlin.de

Abstract

Given two distinct point sets

and

in the plane, we say that

blocks

if no two

points of

are adjacent in any Delaunay triangulation of

P∪Q

. Aichholzer et al. (2013)

showed that any set

points in general position can be blocked by

points and that

every set

points in convex position can be blocked by

points. Moreover, they

conjectured that, if

is in convex position,

blocking points are suﬃcient and necessary.

The necessity was recently shown by Biniaz (2021) who proved that every point set in general

position requires nblocking points.

Here we investigate the variant, where blocking points can only lie outside of the convex

hull of the given point set. We show that

4n−O

(1) such exterior-blocking points are

sometimes necessary, even if the given point set is in convex position. As a consequence

we obtain that, if the conjecture of Aichholzer et al. for the original setting was true, then

minimal blocking sets of some point conﬁgurations

would have to contain points inside of

the convex hull of P.

1 Introduction

Delaunay triangulations, Delaunay graphs, Voronoi diagrams (their dual structures), and various

generalizations have been intensively studied in the last century; see for example the standard

textbook in Computation Geometry [

]. A Delaunay triangulation

(

) of a given point set

in the plane is a triangulation of

in which for every edge between two distinct points

p1, p2∈P

there exists a circle through

p1, p2

that contains no point of

P\ {p1, p2}

in its interior. An edge

spanned by

with this property is called Delaunay edge. For a point set in general position,

that is, no three points of

lie on a common line and no four points of

lie on a common circle,

the Delaunay triangulation is unique. Figure 1(a) shows the unique Delaunay triangulation of a

point set in convex position, that is, the points are the vertices of a convex polygon.

∗

We thank anonymous reviewers for valuable comments. Parada was supported by the Austrian Science Fund

(FWF): W1230 and by Independent Research Fund Denmark grant 2020-2023 (9131-00044B) “Dynamic Network

Analysis”. Scheucher, Parada, and Vogtenhuber were partially supported within the collaborative D-A-CH project

Arrangements and Drawings, by grants DFG: FE 340/12-1 and FWF: I 3340-N35, respectively. Scheucher was

supported by the DFG Grant SCHE 2214/1-1.

arXiv:2210.12015v1 [cs.CG] 21 Oct 2022

(a)

(b)

(c)

Figure 1:

(a) A set

(blue) of ﬁve points in convex position, and its unique Delaunay triangulation

(

). (b) A set

(red) of two points that blocks two of the edges of

(

). (c) A set

of ﬁve points

from the exterior of conv(P) that blocks P.

In this article we continue the investigation of blocking points for Delaunay edges. For two

point sets

P, Q

, we say that

blocks an edge

p1p2

spanned by

if every circle through

contains at least one point of

P∪Q

in its interior. Equivalently,

p1p2

is not an edge of any

Delaunay triangulation of

P∪Q

. We say that

blocks

blocks all edges spanned by

Equivalently, no two points of

are adjacent in any Delaunay triangulation of

P∪Q

. If moreover

no point of

lies in the interior of the convex hull of

, we say that

blocks

from the exterior.

Figures 1(b) and 1(c) shows examples where Qblocks (parts of) P.

Aronov et al. [

] showed that every set

points in general position can be blocked by a

set of 2

n−

2 points, and that, if

is in convex position,

blocking points are suﬃcient. Both

of their bounds were improved by Aichholzer et al. [

], who showed that, for general position,

blocking points are suﬃcient, and that, for convex position,

blocking points are suﬃcient.

They also showed that

n−

1 blocking points are always needed and posed the following conjecture.

Conjecture 1

([

])

is a set of

points in convex position in the plane, then

blocking

points are necessary and suﬃcient, that is, every blocking set of

contains at least

points and

this bound is tight.

Biniaz [

] recently strengthened the lower bound by showing that, for every set of

points

in general position,

blocking points are necessary and that there are sets of

points in

convex position which can be blocked by

points. While this conﬁrms the necessity part from

Conjecture 1, the question about suﬃciency remains open.

For many sets

points in convex position, a simple construction suﬃces to indeed block

all Delaunay edges with exactly

points: place a single point of

close to the mid point of each

edge of the convex hull of

, on the outer side; see Figure 1(c). Placing the points arbitrary

close to the convex hull edges ensures that all those edges are blocked, and indeed every convex

hull edge requires at least one point somewhere outside the convex hull to be blocked. Moreover,

this simple construction often enough also blocks all interior edges of

(

). This may suggest

that a similar approach could actually always work.

Inspired by these observations, we investigate the variant where blocking points have to

lie outside of the convex hull of the given

-point set

. We show that

4n−O

(1) such

exterior-blocking points are sometimes necessary, even if Pis in convex position.

Theorem 1.

For

k∈N

, there is a set

of 4

points in general position that requires at least

5k−5exterior-blocking points.

As a direct consequence of Theorem 1 we obtain for the original setting that, if Conjecture 1

was true, then minimal blocking sets of certain point sets

would have to contain points inside

of the convex hull of P.

Note that the construction of size

4nc

for convex position in [

] might contain interior

points. The reason is that in the induction blocking points placed for a subproblem in the

exterior of an edge (Case (a) in the proof of Theorem 3 in [

]) might end up to be interior for

the overall triangulation. Modifying their approach, a blocking set of size

≈4

can be obtained

by iteratively cutting ears ((n, 3,4)-cuts in the terminology of [1]).

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

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

10 玖币 0人已下载

立即下载

摘要：

BlockingDelaunayTriangulationsfromtheExterior*OswinAichholzer1ThomasHackl1MaartenLoer2AlexanderPilz1IreneParada3ManfredScheucher4BirgitVogtenhuber11InstituteofSoftwareTechnology,GrazUniversityofTechnology,Austriaoaich@ist.tugraz.at,bvogt@ist.tugraz.at2DepartmentofInformationandComputingSciences,Ut...

展开>> 收起<<

Blocking Delaunay Triangulations from the Exterior Oswin Aichholzer1Thomas Hackl1Maarten L oer2Alexander Pilz1 Irene Parada3Manfred Scheucher4Birgit Vogtenhuber1.pdf

共10页,预览2页

还剩页未读，继续阅读

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

Blocking Delaunay Triangulations from the Exterior Oswin Aichholzer1Thomas Hackl1Maarten L oer2Alexander Pilz1 Irene Parada3Manfred Scheucher4Birgit Vogtenhuber1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: