On the number of touching pairs in a set of planar curves

P. Györgyi; B. Hujter; S. Kisfaludi-Bak

doi:10.1016/j.comgeo.2017.10.004

On the number of touching pairs in a set of planar curves

P. Györgyi , B. Hujter , S. Kisfaludi-Bak

Algorithms

Research output: Contribution to journal › Article › Academic › peer-review

4 Citations (Scopus)

212 Downloads (Pure)

Abstract

Given a set of planar curves (Jordan arcs), each pair of which meets — either crosses or touches — exactly once, we establish an upper bound on the number of touchings. We show that such a curve family has O(t ²n) touchings, where t is the number of faces in the curve arrangement that contains at least one endpoint of one of the curves. Our method relies on finding special subsets of curves called quasi-grids in curve families; this gives some structural insight into curve families with a high number of touchings.

Original language	English
Pages (from-to)	29-37
Number of pages	9
Journal	Computational Geometry
Volume	67
Issue number	Januari 2018
DOIs	https://doi.org/10.1016/j.comgeo.2017.10.004
Publication status	Published - Jan 2018

Keywords

Combinatorial geometry;
Touching curves;
Pseudo-segments
Touching curves
Combinatorial geometry

Access to Document

10.1016/j.comgeo.2017.10.004

Publisher versionFinal published version, 451 KB

Cite this

@article{451d5660c9b147229a430026738d7552,

title = "On the number of touching pairs in a set of planar curves",

abstract = "Given a set of planar curves (Jordan arcs), each pair of which meets — either crosses or touches — exactly once, we establish an upper bound on the number of touchings. We show that such a curve family has O(t 2n) touchings, where t is the number of faces in the curve arrangement that contains at least one endpoint of one of the curves. Our method relies on finding special subsets of curves called quasi-grids in curve families; this gives some structural insight into curve families with a high number of touchings. ",

keywords = "Combinatorial geometry; , Touching curves; , Pseudo-segments, Touching curves, Combinatorial geometry",

author = "P. Gy{\"o}rgyi and B. Hujter and S. Kisfaludi-Bak",

year = "2018",

month = jan,

doi = "10.1016/j.comgeo.2017.10.004",

language = "English",

volume = "67",

pages = "29--37 ",

journal = "Computational Geometry",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "Januari 2018",

}

TY - JOUR

T1 - On the number of touching pairs in a set of planar curves

AU - Györgyi , P.

AU - Hujter , B.

AU - Kisfaludi-Bak, S.

PY - 2018/1

Y1 - 2018/1

N2 - Given a set of planar curves (Jordan arcs), each pair of which meets — either crosses or touches — exactly once, we establish an upper bound on the number of touchings. We show that such a curve family has O(t 2n) touchings, where t is the number of faces in the curve arrangement that contains at least one endpoint of one of the curves. Our method relies on finding special subsets of curves called quasi-grids in curve families; this gives some structural insight into curve families with a high number of touchings.

AB - Given a set of planar curves (Jordan arcs), each pair of which meets — either crosses or touches — exactly once, we establish an upper bound on the number of touchings. We show that such a curve family has O(t 2n) touchings, where t is the number of faces in the curve arrangement that contains at least one endpoint of one of the curves. Our method relies on finding special subsets of curves called quasi-grids in curve families; this gives some structural insight into curve families with a high number of touchings.

KW - Combinatorial geometry;

KW - Touching curves;

KW - Pseudo-segments

KW - Touching curves

KW - Combinatorial geometry

UR - http://www.scopus.com/inward/record.url?scp=85031694958&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2017.10.004

DO - 10.1016/j.comgeo.2017.10.004

M3 - Article

SN - 0925-7721

VL - 67

SP - 29

EP - 37

JO - Computational Geometry

JF - Computational Geometry

IS - Januari 2018

ER -

On the number of touching pairs in a set of planar curves

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this