On arrangements of Jordan arcs with three intersections per pair

ABSTRACT

Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union of n regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected Riemann surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan arcs in the upper halfplane starting and ending on the x-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only &THgr;(n&agr;(n)), where &agr;(n) is the extremely slowly growing functional inverse of Ackermann's function.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Motion

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning
      I.4.7 Feature Measurement
          Subjects: Projections
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Computer vision

General Terms:
Algorithms, Design, Measurement, Performance, Theory