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

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

Research output: Contribution to journalArticleAcademicpeer-review

94 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 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.

Original languageEnglish
Pages (from-to)29-37
Number of pages9
JournalComputational Geometry
Volume67
Issue numberJanuari 2018
DOIs
Publication statusPublished - Jan 2018

Keywords

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

Fingerprint

Dive into the research topics of 'On the number of touching pairs in a set of planar curves'. Together they form a unique fingerprint.

Cite this