Header menu link for other important links
X
An optimal algorithm for one-separation of a set of isothetic polygons
Kamala Krithivasan
Published in
2004
Volume: 164
   
Issue: 1-4
Pages: 65 - 88
Abstract
We consider the problem of separating a collection of isothetic polygons in the plane by translating one polygon at a time to infinity. The directions of translation are the four isothetic (parallel to the axes) directions, but a particular polygon can be translated only in one of these four directions. Our algorithm detects whether a scene is separable in this sense and computes a translational ordering of the polygons. The time and space complexities of our algorithm are O(nlogn) and O(n) respectively, where n is the total number of vertices of the polygons in the scene. The best previous algorithm in the plane for this problem has complexities of O(n log2 n) time and O(n log n) space. © 2003 Elsevier Inc. All rights reserved.
About the journal
JournalInformation Sciences
ISSN00200255
Open AccessNo
Concepts (11)
  •  related image
    Algorithms
  •  related image
    Computational geometry
  •  related image
    Computer aided design
  •  related image
    Computer aided manufacturing
  •  related image
    Computer graphics
  •  related image
    Motion planning
  •  related image
    Robot applications
  •  related image
    ISOTHETIC POLYGONS
  •  related image
    OPTIMAL ALGORITHM
  •  related image
    Vertices
  •  related image
    Information science