Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.

  

Convexity Recognition of the Union of Polyhedra

Author(s):

A. Bemporad, K. Fukuda, F.D. Torrisi
Conference/Journal:

vol. AUT00-13
Abstract:

In this paper we consider the following basic problem in polyhedral computation: Given two polyhedra in $R^d$, $P$ and $Q$, decide whether their union is convex, and, if so, compute it. We consider the three natural specializations of the problem: (1) when the polyhedra are given by half-spaces (H-polyhedra) (2) when they are given by vertices and extreme rays (V-polyhedra) (3) when both H- and V-polyhedral representations are available. Both the bounded (polytopes) and the unbounded case are considered. We show that the first two problems are polynomially solvable, and that the third problem is strongly-polynomially solvable.

(last update: July 2000)



Further Information

Year:

2000
Type of Publication:

(04)Technical Report
Supervisor:



File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@TechReport { BemFuk:2000:IFA_62,
    author={A. Bemporad and K. Fukuda and F.D. Torrisi},
    title={{Convexity Recognition of the Union of Polyhedra}},
    institution={},
    year={2000},
    number={},
    address={},
    month=apr,
    url={http://control.ee.ethz.ch/index.cgi?page=publications;action=details;id=62}
}
Permanent link