×

On movable separability and isotheticity. (English) Zbl 0744.52001

Summary: The paper is concerned with the movable-separability properties of isothetic simple polygons. Previously obtained results in this area were applied only to the highly restricted class of star-shaped isothetic polygons. We introduce new classes of isothetic polygons which are substantially more general, and establish their movable-separability properties. We also define new structures called separability hulls of isothetic polygons, and introduce the notion of a jagged cross, which is a very broad subclass of isothetic simple polygons with highly interesting geometry. Elegant results on the separability-related properties of these structures are shown. Although occasional remarks on algorithmic aspects are made, the emphasis is more on structural geometric properties of isothetic polygons that on algorithmic implications, which are open for further investigation.

MSC:

52A10 Convex sets in \(2\) dimensions (including convex curves)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dehne, F.; Sack, J. R., Separability of Sets of Polygons, (Tech. Rep. SCS-TR-82 (Aug. 1986), School of Computer Science, Carleton Univ: School of Computer Science, Carleton Univ Ottawa) · Zbl 0643.68048
[2] Hopcroft, J. E.; Schwartz, J. T.; Sharir, M., On the complexity of motion planning for multiple independent objects; pspace-hardness of the “warehouseman”s problem,”, Internat. J. Robotics Res., 3, 76-88 (1984)
[3] Pollack, R.; Sharir, M.; Siffrony, S., Separating two simple polygons by a sequence of translations, Discrete Comput. Geom., 3, 123-136 (1988) · Zbl 0646.68052
[4] Preparata, F. P.; Shamos, M. I., Computational Geometry: An Introduction (1985), Springer-Verlag · Zbl 0575.68059
[5] Toussaint, G. T., Movable separability of sets, (Toussaint, G. T., Computational Geometry (1985), North-Holland), 335-375 · Zbl 0588.68053
[6] Wood, D., An isothetic view of computational geometry, (Toussaint, G. T., Computational Geometry (1985), North-Holland), 429-459
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.