An optimal algorithm for one-separation of a set of isothetic polygons

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 directi...

Full description

Saved in:
Bibliographic Details
Published in:Information sciences 2004-08, Vol.164 (1), p.65-88
Main Authors: Datta, Amitava, Krithivasan, Kamala, Ottmann, Thomas
Format: Article
Language:English
Subjects:
Computational geometry
Isothetic polygons
Motion planning
One-separation
Optimal algorithm
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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( nlog n) 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( nlog 2 n) time and O( nlog n) space.
ISSN:0020-0255
1872-6291
DOI:10.1016/j.ins.2003.06.007