Subscribe: cs.CG updates on
Preview: cs.CG updates on

cs.CG updates on

Computer Science -- Computational Geometry (cs.CG) updates on the e-print archive

Published: 2017-09-20T20:30:00-05:00


Parameterization of configuration space obstacles in three-dimensional rotational motion planning. (arXiv:1709.06601v1 [cs.CG])

This study investigates the exact geometry of the configuration space in three-dimensional rotational motion planning. A parameterization of configuration space obstacles is derived for a given triangulated or ball-approximated scene with an object rotating around a given point. The results obtained are an important step towards a complete description of the rich structure of a configuration space in three-dimensional rotational motion planning.

Drawing Graphs on Few Circles and Few Spheres. (arXiv:1709.06965v1 [cs.CG])

Given a drawing of a graph, its visual complexity is defined as the number of geometrical entities in the drawing, for example, the number of segments in a straight-line drawing or the number of arcs in a circular-arc drawing (in 2D). Recently, Chaplick et al. introduced a different measure for the visual complexity, the affine cover number, which is the minimum number of lines (or planes) that together cover a straight-line drawing of a graph $G$ in 2D (3D). In this paper, we introduce the spherical cover number, which is the number of circles (or spheres) that together cover a circular-arc drawing in 2D (or 3D). It turns out that spherical covers are sometimes significantly smaller than affine covers. Moreover, there are highly symmetric graphs that have symmetric optimum spherical covers but apparently no symmetric optimum affine cover. For complete, complete bipartite, and platonic graphs, we analyze their spherical cover numbers and compare them to their affine cover numbers as well as their segment and arc numbers. We also link the spherical cover number to other graph parameters such as chromatic number, treewidth, and linear arboricity.