Some Geometric Applications of Anti-Chains

Sariel Har-Peled, Mitchell Jones

Research output: Contribution to conferencePaperpeer-review


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)
Number of pages6
StatePublished - 2020
Event32nd Canadian Conference on Computational Geometry, CCCG 2020 - Saskatoon, Canada
Duration: Aug 5 2020Aug 7 2020


Conference32nd Canadian Conference on Computational Geometry, CCCG 2020

ASJC Scopus subject areas

  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'Some Geometric Applications of Anti-Chains'. Together they form a unique fingerprint.

Cite this