The Lifting Model for Reconfiguration

Given a pair of start and target configurations, each consisting of n pairwise disjoint disks in the plane, what is the minimum number of moves that suffice for transforming the start configuration into the target configuration? In one move a disk is lifted from the plane and placed back in the plan...

Full description

Saved in:
Bibliographic Details
Published in:Discrete & computational geometry 2006-05, Vol.35 (4), p.653-669
Main Authors: Bereg, Sergey, Dumitrescu, Adrian
Format: Article
Language:English
Subjects:
Algorithms
Disks
Geometry
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a pair of start and target configurations, each consisting of n pairwise disjoint disks in the plane, what is the minimum number of moves that suffice for transforming the start configuration into the target configuration? In one move a disk is lifted from the plane and placed back in the plane at another location, without intersecting any other disk. We discuss efficient algorithms for this task and estimate their number of moves under different assumptions on disk radii. We then extend our results for arbitrary disks to systems of pseudodisks, in particular to sets of homothetic copies of a convex object. [PUBLICATION ABSTRACT]
ISSN:0179-5376
1432-0444
DOI:10.1007/s00454-006-1239-x