×

Sweeping an oval to a vanishing point. (English) Zbl 1230.68205

Summary: Given a convex region in the plane, and a sweep-line as a tool, what is the best way to reduce the region to a single point by a sequence of sweeps? The problem of sweeping points by orthogonal sweeps was first studied in [A. Dumitrescu and M. Jiang, Algorithmica 60, No. 3, 703–717 (2011; Zbl 1218.68184)]. Here we consider the following slanted variant of sweeping, recently introduced in [Y. Bousany, M. L. Karker, J. O’Rourke and L. Sparaco, “Sweeping minimum perimeter enclosing parallelograms: optimal crumb cleanup”, in: Proceedings of the 22nd Canadian conference on computational geometry (CCCG) 2010. 167–170 (2010), http://cs.umanitoba.ca/~cccg2010/program.html]: in a single sweep, the sweep-line is placed at a start position somewhere in the plane, then moved continuously according to a sweep vector \(\vec v\) (not necessarily orthogonal to the sweep-line) to another parallel end position, and then lifted from the plane. The cost of a sequence of sweeps is the sum of the lengths of the sweep vectors. The optimal sweeping cost of a region is the infimum of the costs over all finite sweeping sequences for that region. An optimal sweeping sequence for a region is one with a minimum total cost, if it exists. Another parameter of interest is the number of sweeps.
We show that there exist convex regions for which the optimal sweeping cost cannot be attained by two sweeps. This disproves a conjecture of Bousany et al. stating that two sweeps (with vectors along the two adjacent sides of a minimum-perimeter enclosing parallelogram) always suffice. Moreover, we conjecture that for some convex regions, no finite sweeping sequence is optimal. On the other hand, we show that both the 2-sweep algorithm based on the minimum-perimeter enclosing rectangle and the 2-sweep algorithm based on the minimum-perimeter enclosing parallelogram achieve a \(4/\pi \approx 1.27\) approximation of the optimal sweeping cost in this model.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W25 Approximation algorithms
52B55 Computational aspects related to convexity

Citations:

Zbl 1218.68184
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Y. Bousany, M.L. Karker, J. O’Rourke, L. Sparaco, Sweeping minimum perimeter enclosing parallelograms: optimal crumb cleanup, in: Proceedings of the 22nd Canadian Conference on Computational Geometry, CCCG 2010, Winnipeg, Manitoba, Canada, August 2010, pp. 167-170. Full version online at: http://www.cs.umanitoba.ca/ cccg2010/program.htmlhttp://maven.smith.edu/ orourke/Papers/SweepTwiceFull.pdf; Y. Bousany, M.L. Karker, J. O’Rourke, L. Sparaco, Sweeping minimum perimeter enclosing parallelograms: optimal crumb cleanup, in: Proceedings of the 22nd Canadian Conference on Computational Geometry, CCCG 2010, Winnipeg, Manitoba, Canada, August 2010, pp. 167-170. Full version online at: http://www.cs.umanitoba.ca/ cccg2010/program.htmlhttp://maven.smith.edu/ orourke/Papers/SweepTwiceFull.pdf
[2] Dumitrescu, A.; Jiang, M., Sweeping points, Algorithmica, 60, 703-717 (2011) · Zbl 1218.68184
[3] Mitchell, J. S.B.; Polishchuk, V., Minimum-perimeter enclosures, Information Processing Letters, 107, 120-124 (2008) · Zbl 1186.68509
[4] Yaglom, I. M.; Boltyanskiĭ, V. G., Convex Figures (1961), Holt, Rinehart and Winston: Holt, Rinehart and Winston New York · Zbl 0098.35501
[5] P. Żyliński, Personal communication, June 2007.; P. Żyliński, Personal communication, June 2007.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.