Some Geometric Applications of Anti-Chains

Sariel Har-Peled, Mitchell Jones

Research output: Contribution to conferencePaperpeer-review

Abstract

We present an algorithmic framework for computing anti-chains of maximum size in geometric posets. Specifically, posets in which the entities are geometric objects, where comparability of two entities is implicitly defined but can be efficiently tested. Computing the largest anti-chain in a poset can be done in polynomial time via maximum-matching in a bipartite graph, and this leads to several efficient algorithms for the following problems, each running in (roughly) O(n3/2) time: (A) Computing the largest Pareto-optimal subset of a set of n points in ℝd. (B) Given a set of disks in the plane, computing the largest subset of disks such that no disk contains another. This is quite surprising, as the independent version of this problem is computationally hard. (C) Given a set of axis-aligned rectangles, computing the largest subset of non-crossing rectangles.

Original languageEnglish (US)
Pages326-331
Number of pages6
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 'Some Geometric Applications of Anti-Chains'. Together they form a unique fingerprint.

Cite this