The lifting model for reconfiguration

被引:12
作者
Bereg, S
Dumitrescu, A
机构
[1] Univ Texas, Dept Comp Sci, Richardson, TX 75083 USA
[2] Univ Wisconsin, Dept Comp Sci, Milwaukee, WI 53211 USA
关键词
Reconfiguration;
D O I
10.1007/s00454-006-1239-x
中图分类号
TP301 [理论、方法];
学科分类号
081202 [计算机软件与理论];
摘要
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.
引用
收藏
页码:653 / 669
页数:17
相关论文
共 14 条
[1]
ABELLANAS M, IN PRESS COMPUTATION
[2]
Alon N., 2000, PROBABILISTIC METHOD
[3]
[Anonymous], 2000, Geometry, Spinors and Applications
[4]
Bereg S, 2005, LECT NOTES COMPUT SC, V3742, P37
[5]
Danzer Ludwig, 1963, P S PURE MATH, VVII, P101
[6]
DEMAINE E, 2002, MORE GAMES NO CHANCE, P405
[7]
DUMITRESCU A, 2004, P 20 ANN S COMP GEOM, V116
[8]
GARDNER M, 1975, MATH CARNIVAL, P12
[9]
COMPUTING A CENTERPOINT OF A FINITE PLANAR SET OF POINTS IN LINEAR-TIME [J].
JADHAV, S ;
MUKHOPADHYAY, A .
DISCRETE & COMPUTATIONAL GEOMETRY, 1994, 12 (03) :291-312
[10]
New techniques for exact and approximate dynamic closest-point problems [J].
Kapoor, S ;
Smid, M .
SIAM JOURNAL ON COMPUTING, 1996, 25 (04) :775-796