Supporting Ruled Polygons

CCCG: The Canadian Conference in Computational Geometry
2017

We explore several problems related to ruled polygons. Given a ruling of a polygon P, we consider the Reeb graph of P induced by the ruling. We define the Reeb complexity of P, which roughly equates to the minimum number of points necessary to support P. We give asymptotically tight bounds on the Reeb complexity that are also tight up to a small additive constant. When restricted to the set of parallel rulings, we show that the Reeb complexity can be computed in polynomial time.

@inproceedings{cavanna17supporting, Author = {Nicholas J. Cavanna and Marc Khoury and Donald R. Sheehy}, Booktitle = {Proceedings of the Canadian Conference on Computational Geometry}, Title = {Supporting Ruled Polygons}, Year = {2017}}