Discrete Helly type theorems

Frederik Brinck Jensen, Aadi Joshi, Saurabh Ray

Research output: Contribution to conferencePaperpeer-review

Abstract

We show the following discrete Helly-type results in the plane. Let P be a set of points and D a family of convex pseudodisks in the plane s.t. every triple of pseudodisks in D intersects at a point in P. Then, two of the points in P hit all pseudodisks in D. Three similar results that we prove with the roles of points and regions exchanged are the following: let P be a set of points and H a set of halfspaces in the plane s.t. every triple of points from P is covered by some halfspace in H. Then, two of the halfspaces in H cover all points in P. If, instead, every pair of points in P is covered by some halfspace in H, we show that three of halfspaces in H suffice to cover all points in P. Finally, we show that if every pair of points is covered by an axis-parallel rectangle, then five rectangles are required to cover all points.

Original languageEnglish (US)
Pages332-335
Number of pages4
StatePublished - 2020
Event32nd Canadian Conference on Computational Geometry, CCCG 2020 - Saskatoon, Canada
Duration: Aug 5 2020Aug 7 2020

Conference

Conference32nd Canadian Conference on Computational Geometry, CCCG 2020
Country/TerritoryCanada
CitySaskatoon
Period8/5/208/7/20

ASJC Scopus subject areas

  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Discrete Helly type theorems'. Together they form a unique fingerprint.

Cite this