Parallel Algorithms for Chains and Anti-Chains of Points on a Plane

摘要

In this paper we describe efficient parallel algorithms for computing canonical chains and canonical anti-chains partition of a set of points on a plane. The problem to compute chain and anti-chain partition is of interest in VLSI design [LS92], computational geometry [MW92] and in computational molecular biology [Pev01]. A new affine transformation on the set of points is defined which transforms chains in the original point set into anti-chains in the transformed point set.