## Abstract The purpose of this article is to present an algorithm for globally maximizing the ratio of two convex functions __f__ and __g__ over a convex set __X__. To our knowledge, this is the first algorithm to be proposed for globally solving this problem. The algorithm uses a branch and bound
A three-point convexity property and the union of two convex sets
โ Scribed by Karsten Juul
- Publisher
- Springer
- Year
- 1977
- Tongue
- English
- Weight
- 478 KB
- Volume
- 6
- Category
- Article
- ISSN
- 0046-5755
No coin nor oath required. For personal study only.
โฆ Synopsis
In his paper [3], F.A.Valentine has defined a three-point property Pa. The first part of that paper contains results valid in n-space. In the second part is specialized to the plane, and among other things it is proved that a set is the union of two convex sets if it has the property P3 and there is not a finite, odd number > 1 of isolated points of local non-convexity. This is not a necessary condition, and in their paper [1], W. L. Stamey and J. M. Marr gave properties which together with Valentine's results constitute a sufficient condition, which for bounded sets is necessary too. Theorem 2 of the present paper is another improvement on Valentine's result, which for an arbitrary (closed, connected) plane set gives a necessary and sufficient condition that it be the union of two convex sets. This result is formulated and proved with the aid of a new apparatus of concepts, which we first introduce, and which makes it possible to avoid the division into several cases of the proof that is found in [3]. This apparatus of concepts is" also used in Theorem 1, which characterizes the sets fulfilling Pa.
TERMINOLOGY
Everything takes place in the plane II.
The interior, closure, boundary, and convex hull of a set S are denoted by int S, el S, bd S, and conv S respectively. For sets S and X, the relative interior and the relative boundary of S n X with respect to X are denoted by intr(X; S) and bdr(X; S) respectively. If R denotes an open half-line, then -R denotes the unique open half-line which is different from R, is contained in the same line as R, and has the same end point as R. The closed, the open, and the half-open segments with end points x and y are denoted by [x, y], Ix, y[, ]x, y], and [x, y[ respectively. For any points x, y, and z the symbol A(x, y, z) denotes int conv{x, y, z}.
Let x and y be different points. Then L(x, y) denotes the unique line containing x and y, and R(x; y) denotes the unique open half-line containing y and having x as its end point. If z is a point not contained in L(x, y), then H(x, y; z) denotes the unique open half-plane containing z and having L(x, y) as its boundary.
For different points x and y the symbol H~(x, y) denotes the open half-plane to the left of L(x, y), this being orientated in the direction from x to y. If R = cl R(x; y), we also write H,(R) for H,(x, y). Similarly, H,(x, y) and Hr(R) denote the open half-planes to the right.
๐ SIMILAR VOLUMES
An algorithm is described to determine the minimum area polar set of a planar convex polygon described in terms of its vertices. We adopt a result due to Santalo to verify our minimizing solution, and then demonstrate the search procedure on a few examples. 'For triangular (and centrally symmetric)