改进的平面覆盖路径界限-计算机科学-机器学习-算法.pdfVIP

改进的平面覆盖路径界限

HugoA.Akitaya1GregAloupis2AhmadBiniaz3ProsenjitBose4

Jean-LouDeCarufel5CyrilGavoille6JohnIacono7LindaKleist8

MichielSmid4DianeSouvaine9LeonidasTheocharous5

摘要

对于平面上的有限点集，一个覆盖路径是一个多边形路径，使得的每个点都位于该路径

本的一个线段上。路径的顶点不必在的点处。如果一条覆盖路径的线段不相互交叉，则它是平

译面。令为最小的数，使得平面上任意一组点都存在一条至多由段组成的平面覆盖路

中径。我们证明了。这改进了Biniaz（SoCG2023）给出的最佳已知上界。

我们的证明是构造性的，并提供了一个简单的log时间算法来计算平面覆盖路径。

1

v

7

71介绍

4

6

0.在平面上通过多边形路径遍历点的问题是离散几何和计算几何的基础，从组合和计算的角度都

7对其进行过研究。例如，可以参考通过一条不交叉的路径[3,14]遍历一组点，或者通过一条使总

0

5

21MinerSchoolofComputerInformationSciences,UniversityofMassachusetts,Lowell,USA,

:

vhugo_akitaya@.SupportedbytheNSFawardCCF-2348067.

i2KhouryCollegeofComputerSciences,NortheasternUniversity,Boston,MA,USA,

x

rg.aloupis@.

a

3SchoolofComputerScience,UniversityofWindsor,Windsor,Canada,abiniaz@uwindsor.ca.Supportedinpart

byNSERC.

4SchoolofComputerScience,CarletonUniversity,Ottawa,ON,Canada,jit@scs.carleton.ca,

michiel@scs.carleton.ca.SupportedinpartbyNSERC.

5SchoolofElectricalEngineeringandComputerScience,UniversityofOttawa,Ottawa,ON,Canada,

jdecaruf@uottawa.ca,leotheocharous3@.SupportedinpartbyNSERC.

6LaBRI,UniversityofBordeaux,France,gavoille@labri.fr.SupportedbytheFrenchANRprojectsANR-22-

CE48-0001(TEMPOGRAL)andANR-24-CE48-7768-01(ENEDISC).

7DepartmentofComputerScience,UniversitélibredeBruxelles,Brussels,Belgium.Thisworkwassupportedby

theFondsdelaRechercheScientifique-FNRS.

8DepartmentofComputerScience,UniversitätPotsdam,Potsdam,Germany,kleist@cs.uni-potsdam.de.