Convexity recognition of the union of polyhedra

被引：64

作者：

Bemporad, A

Fukuda, K

Torrisi, FD

机构：

[1] ETH Zurich, Automat Control Lab, CH-8092 Zurich, Switzerland

[2] Univ Siena, Dipartimento Engn Informazione, I-53100 Siena, Italy

[3] ETH Zurich, Inst Operat Res, CH-8092 Zurich, Switzerland

[4] Ecole Polytech Fed Lausanne, Dept Math, CH-1015 Lausanne, Switzerland

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2001年 / 18卷 / 03期

关键词：

polyhedron; union; convexity;

D O I：

10.1016/S0925-7721(01)00004-9

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper we consider the following basic problem in polyhedral computation: Given two polyhedra in R-d, P and e, 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 halfspaces (H-polyhedra), (2) when they are given by vertices and extreme rays (V-polyhedra), and (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. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：141 / 154

页数：14

共 13 条

[1] [Anonymous], 1997, HDB DISCRETE COMPUTA
[2] The union of convex polyhedra in three dimensions
Aronov, B
Sharir, M
Tagansky, B
[J]. SIAM JOURNAL ON COMPUTING, 1997, 26 (06) : 1670 - 1688
[3] ON THE CONVEX-HULL OF THE UNION OF CERTAIN POLYHEDRA
BALAS, E
[J]. OPERATIONS RESEARCH LETTERS, 1988, 7 (06) : 279 - 283
[4] Bemporad A, 2000, P AMER CONTR CONF, P872, DOI 10.1109/ACC.2000.876624
[5] BEMPORAD A, 2000, AUT0013 ETH
[6] ERICKSON J, COMPUTATIONAL GEOMET
[7] FINSCHI L, 2000, COMMUNICATION
[8] Franklin W. R., 1982, Proceedings of Graphics Interface '82, P73
[9] FUKUDA K, POLYHEDRAL COMPUTATI
[10] Grunbaum B., 1967, Pure and Applied Mathematics, V16

← 1 2 →