caa a22 4500 445804327 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110701xx s 000 0 eng 10.1007/s00453-009-9364-6 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9364-6 Sweeping Points [Elektronische Daten] [Adrian Dumitrescu, Minghui Jiang] Given a set of points in the plane, and a sweep-line as a tool, what is best way to move the points to a target point using a sequence of sweeps? In a sweep, the sweep-line is placed at a start position somewhere in the plane, then moved orthogonally and continuously to another parallel end position, and then lifted from the plane. The cost of a sequence of sweeps is the total length of the sweeps. Another parameter of interest is the number of sweeps. Four variants are discussed, depending on whether the target is a hole or a pile, and whether the target is specified or freely selected by the algorithm. Here we present a ratio 4/π≈1.27 approximation algorithm in the length measure, which performs at most four sweeps. We also prove that, for the two constrained variants, there are sets of n points for which any sequence of minimum cost requires 3n/2−O(1) sweeps. Springer Science+Business Media, LLC, 2009 Computational geometry nationallicence Sweep-line nationallicence Approximation algorithms nationallicence Dumitrescu Adrian Department of Computer Science, University of Wisconsin-Milwaukee, 53201-0784, Milwaukee, WI, USA aut Jiang Minghui Department of Computer Science, Utah State University, 84322-4205, Logan, UT, USA aut Algorithmica Springer-Verlag 60/3(2011-07-01), 703-717 0178-4617 60:3<703 2011 60 453 https://doi.org/10.1007/s00453-009-9364-6 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9364-6 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dumitrescu Adrian Department of Computer Science, University of Wisconsin-Milwaukee, 53201-0784, Milwaukee, WI, USA aut NATIONALLICENCE 700 1- Jiang Minghui Department of Computer Science, Utah State University, 84322-4205, Logan, UT, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/3(2011-07-01), 703-717 0178-4617 60:3<703 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer