ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Books
  • Journals
  • Articles  (112)
  • Computational geometry  (57)
  • global optimization  (55)
  • Springer  (112)
  • MDPI Publishing
  • Oxford University Press
  • 1990-1994  (112)
  • 1955-1959
  • Mathematics  (112)
Collection
  • Books
  • Journals
  • Articles  (112)
Source
Keywords
Publisher
  • Springer  (112)
  • MDPI Publishing
  • Oxford University Press
Years
Year
Topic
  • 1
    Electronic Resource
    Electronic Resource
    A workbench for computational geometry (1994)
    Springer
    Algorithmica 11 (1994), S. 404-428 
    Details
    ISSN: 1432-0541
    Keywords: Algorithms ; Computational geometry ; Implementation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe the design and implementation of a workbench for computational geometry. We discuss issues arising from this implementation, including comparisons of different algorithms for constant factors, code size, and ease of implementation. The workbench is not just a library of computational geometry algorithms and data structures, but is designed as a geometrical programming environment, providing tools for: creating, editing, and manipulating geometric objects; demonstrating and animating geometric algorithms; and, most importantly, for implementing and maintaining complex geometric algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187021
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    An improved technique for output-sensitive hidden surface removal (1994)
    Springer
    Algorithmica 11 (1994), S. 469-484 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Hidden surface removal ; Ray shooting
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We derive a new output-sensitive algorithm for hidden surface removal in a collection ofn triangles, viewed from a pointz such that they can be ordered in an acyclic fashion according to their nearness toz. Ifk is the combinatorial complexity of the outputvisibility map, then we obtain a sophisticated randomized algorithm that runs in (randomized) timeO(n4/3 log2.89 n +k 3/5 n 4/5 + δ for anyδ 〉 0. The method is based on a new technique for tracing the visible contours using ray shooting.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01293267
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    A provably fast linear-expected-time maxima-finding algorithm (1994)
    Springer
    Algorithmica 11 (1994), S. 501-524 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Maxima ; Probabilistic analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In a recent paper Bentleyet al. [1] presented some fast (low-multiplicative constants) linear-expected-time algorithms for finding the maxima ofN points chosen independently identically distributed (i.i.d.) from a Component Independent (CI) distribution. They also presented another algorithm, the Move-To-Front (MTF) algorithm, which empirical evidence suggests runs faster than the other algorithms. They conjectured that the MTF algorithm runs inN+o(N) expected time. In this paper we prove their conjecture forN points chosen i.i.d. from any two-dimensional distribution. The proof mixes probabilistic and amortized techniques.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189991
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Point placement algorithms for Delaunay triangulation of polygonal domains (1994)
    Springer
    Algorithmica 12 (1994), S. 1-17 
    Details
    ISSN: 1432-0541
    Keywords: Delaunay triangulation ; Polygonal domain ; Finite-element mesh generation ; Edge-free circle ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In some applications of triangulation, such as finite-element mesh generation, the aim is to triangulate a given domain, not just a set of points. One approach to meeting this requirement, while maintaining the desirable properties of Delaunay triangulation, has been to enforce the empty circumcircle property of Delaunay triangulation, subject to the additional constraint that the edges of a polygon be covered by edges of the triangulation. In finite-element mesh generation it is usually necessary to include additional points besides the vertices of the domain boundary. This motivates us to ask whether it is possible to trinagulate a domain by introducing additional points in such a manner that the Delaunay triangulation of the points includes the edges of the domain boundary. We present algorithms that given a multiply connected polygonal domain withN vertices, placeK additional points on the boundary inO(N logN + K) time such that the polygon is covered by the edges of the Delaunay triangulation of theN + K points. Furthermore,K is the minimum number of additional points such that a circle, passing through the endpoints of each boundary edge segment, exists that does not contain in its interior any other part of the domain boundary. We also show that by adding only one more point per edge, certain degeneracies that may otherwise arise can be avoided.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377180
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    An optimal algorithm for the on-line closest-pair problem (1994)
    Springer
    Algorithmica 12 (1994), S. 18-29 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Closest pair ; Point location ; Centroid ; Amortization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give an algorithm that computes the closest pair in a set ofn points ink-dimensional space on-line, inO(n logn) time. The algorithm only uses algebraic functions and, therefore, is optimal. The algorithm maintains a hierarchical subdivision ofk-space into hyperrectangles, which is stored in a binary tree. Centroids are used to maintain a balanced decomposition of this tree.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377181
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Ray shooting in polygons using geodesic triangulations (1994)
    Springer
    Algorithmica 12 (1994), S. 54-68 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray-shooting ; Triangulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetP be a simple polygon withn vertices. We present a simple decomposition scheme that partitions the interior ofP intoO(n) so-called geodesic triangles, so that any line segment interior toP crosses at most 2 logn of these triangles. This decomposition can be used to preprocessP in a very simple manner, so that any ray-shooting query can be answered in timeO(logn). The data structure requiresO(n) storage andO(n logn) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time toO(n). We also extend our general technique to the case of ray shooting amidstk polygonal obstacles with a total ofn edges, so that a query can be answered inO(√ logn) time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377183
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors (1994)
    Springer
    Algorithmica 12 (1994), S. 421-435 
    Details
    ISSN: 1432-0541
    Keywords: Spanning tree ; Steiner tree ; Heuristic algorithm ; Computational geometry ; Rectilinear distance ; Nearest neighbor ; Geographic nearest neighbor ; Decomposable search problem ; Range tree
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n 2 log n) toO(n log2 n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188713
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Efficient ray shooting and hidden surface removal (1994)
    Springer
    Algorithmica 12 (1994), S. 30-53 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray shooting ; Multilevel data structures ; Hidden surface removal ; Output-sensitive
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we study the ray-shooting problem for three special classes of polyhedral objects in space: axis-parallel polyhedra, curtains (unbounded polygons with three edges, two of which are parallel to thez-axis and extend downward to minus infinity), and fat horizontal triangles (triangles parallel to thexy-plane whose angles are greater than some given constant). For all three problems structures are presented usingO(n 2+ɛ) preprocessing, for any fixedɛ 〉 0, withO(logn) query time. We also study the general ray-shooting problem in an arbitrary set of triangles. Here we present a structure that usesOn 4+ɛ) preprocessing and has a query time ofO(logn). We use the ray-shooting structure for curtains to obtain an algorithm for computing the view of a set of nonintersecting prolyhedra. For any ɛ 〉 0, we can obtain an algorithm with running time $$O(n^{1 + \varepsilon } \sqrt k )$$ , wheren is the total number of vertices of the polyhedra andk is the size of the output. This is the first output-sensitive algorithm for this problem that does not need a depth order on the faces of the polyhedra.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377182
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Algorithms for bichromatic line-segment problems and polyhedral terrains (1994)
    Springer
    Algorithmica 11 (1994), S. 116-132 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Line-segment intersection ; Segment trees ; Lines in space ; Polyhedral terrains ; Deterministic and randomized algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider a variety of problems on the interaction between two sets of line segments in two and three dimensions. These problems range from counting the number of intersecting pairs between m blue segments andn red segments in the plane (assuming that two line segments are disjoint if they have the same color) to finding the smallest vertical distance between two nonintersecting polyhedral terrains in three-dimensional space. We solve these problems efficiently by using a variant of the segment tree. For the three-dimensional problems we also apply a variety of recent combinatorial and algorithmic techniques involving arrangements of lines in three-dimensional space, as developed in a companion paper.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182771
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Variations on ray shooting (1994)
    Springer
    Algorithmica 11 (1994), S. 133-145 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray shooting ; Half-plane range searching ; ES-trees
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We solve some problems related toray shooting in the plane, such as finding the first object hit by a query ray or counting the number of objects intersected by the query line. Our main results are an algorithm for finding the first hit when the objects are lines, and an algorithm for the case when the objects are segments. If the segments form simple polygons, this information can be used for reducing the complexity of the algorithms. The algorithms are efficient in space and in query time. Moreover, they are simple and therefore of practical use.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182772
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    A quasiconcave minimization method for solving linear two-level programs (1994)
    Springer
    Journal of global optimization 4 (1994), S. 243-263 
    Details
    ISSN: 1573-2916
    Keywords: Linear two-level program ; global optimization ; Stackelberg game ; quasiconcave minimization ; branch and bound ; outer approximation ; subdivision procedure
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper the linear two-level problem is considered. The problem is reformulated to an equivalent quasiconcave minimization problem, via a reverse convex transformation. A branch and bound algorithm is developed which takes the specific structure into account and combines an outer approximation technique with a subdivision procedure.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01098360
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    Electronic Resource
    Electronic Resource
    Simulated annealing for constrained global optimization (1994)
    Springer
    Journal of global optimization 5 (1994), S. 101-126 
    Details
    ISSN: 1573-2916
    Keywords: Continuous simulated annealing ; adaptive cooling ; random search ; global optimization ; Monte Carlo optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Hide-and-Seek is a powerful yet simple and easily implemented continuous simulated annealing algorithm for finding the maximum of a continuous function over an arbitrary closed, bounded and full-dimensional body. The function may be nondifferentiable and the feasible region may be nonconvex or even disconnected. The algorithm begins with any feasible interior point. In each iteration it generates a candidate successor point by generating a uniformly distributed point along a direction chosen at random from the current iteration point. In contrast to the discrete case, a single step of this algorithm may generateany point in the feasible region as a candidate point. The candidate point is then accepted as the next iteration point according to the Metropolis criterion parametrized by anadaptive cooling schedule. Again in contrast to discrete simulated annealing, the sequence of iteration points converges in probability to a global optimum regardless of how rapidly the temperatures converge to zero. Empirical comparisons with other algorithms suggest competitive performance by Hide-and-Seek.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01100688
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    Electronic Resource
    Electronic Resource
    Construction of test problems for a class of reverse convex programs (1994)
    Springer
    Journal of optimization theory and applications 81 (1994), S. 343-354 
    Details
    ISSN: 1573-2878
    Keywords: Reverse convex programming ; nonconvex programming ; nonlinear programming ; linear programming ; test problems ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A method of constructing test problems with known global solution for a class of reverse convex programs or linear programs with an additional reverse convex constraint is presented. The initial polyhedron is assumed to be a hypercube. The method then systematically generates cuts that slice the cube in such a way that a prespecified global solution on its edge remains intact. The proposed method does not require the solution of linear programs or systems of linear equations as is often required by existing techniques.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02191668
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 14
    Electronic Resource
    Electronic Resource
    Accelerations for a variety of global optimization methods (1994)
    Springer
    Journal of global optimization 4 (1994), S. 37-45 
    Details
    ISSN: 1573-2916
    Keywords: Multidimensional bisection ; deterministic ; global optimization ; mathematical programming ; search
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Optimization methods for a given class are easily modified to utilize additional information and work faster on a more restricted class. In particular algorithms that use only the Lipschitz constant (e.g. Mladineo, Piyavskii, Shubert and Wood) can be modified to use second derivative bounds or gradient calculations. The algorithm of Breiman & Cutler can be modified to use Lipschitz bounds. Test cases illustrating accelerations to various algorithms are provided.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096533
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 15
    Electronic Resource
    Electronic Resource
    The simplex method as a global optimizer: A c-programming perspective (1994)
    Springer
    Journal of global optimization 4 (1994), S. 89-109 
    Details
    ISSN: 1573-2916
    Keywords: Linear programming ; simplex method ; c-programming ; composite functions ; global optimization ; dc problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper we give a brief account of the important role that the conventional simplex method of linear programming can play in global optimization, focusing on its collaboration with composite concave programming techniques. In particular, we demonstrate how rich and powerful the c-programming format is in cases where its parametric problem is a standard linear programming problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096536
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    Electronic Resource
    Electronic Resource
    Optimization methods for computing global minima of nonconvex potential energy functions (1994)
    Springer
    Journal of global optimization 4 (1994), S. 117-133 
    Details
    ISSN: 1573-2916
    Keywords: Molecular conformation ; protein folding ; nonconvex potential functions ; global optimization ; simulated annealing ; parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The minimization of potential energy functions plays an important role in the determination of ground states or stable states of certain classes of molecular clusters and proteins. In this paper we introduce some of the most commonly used potential energy functions and discuss different optimization methods used in the minimization of nonconvex potential energy functions. A very complete bibliography is also given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096719
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 17
    Electronic Resource
    Electronic Resource
    A generalization of the construction of test problems for nonconvex optimization (1994)
    Springer
    Journal of global optimization 5 (1994), S. 21-34 
    Details
    ISSN: 1573-2916
    Keywords: Reverse convex programs ; concave programs ; test problems ; nonconvex problems ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper we adopt and generalize the basic idea of the method presented in [3] and [4] to construct test problems that involve arbitrary, not necessarily quadratic, concave functions, for both Concave Minimization and Reverse Convex Programs
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01097001
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 18
    Electronic Resource
    Electronic Resource
    A finite concave minimization algorithm using branch and bound and neighbor generation (1994)
    Springer
    Journal of global optimization 5 (1994), S. 1-14 
    Details
    ISSN: 1573-2916
    Keywords: Concave minimization ; branch and bound ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this article we present a new finite algorithm for globally minimizing a concave function over a compact polyhedron. The algorithm combines a branch and bound search with a new process called neighbor generation. It is guaranteed to find an exact, extreme point optimal solution, does not require the objective function to be separable or even analytically defined, requires no nonlinear computations, and requires no determinations of convex envelopes or underestimating functions. Linear programs are solved in the branch and bound search which do not grow in size and differ from one another in only one column of data. Some preliminary computational experience is also presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096999
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 19
    Electronic Resource
    Electronic Resource
    Molecular conformation on the CM-5 by parallel two-level simulated annealing (1994)
    Springer
    Journal of global optimization 4 (1994), S. 187-208 
    Details
    ISSN: 1573-2916
    Keywords: Molecular conformation ; global optimization ; simulated annealing ; parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper, we propose a new kind of simulated annealing algorithm calledtwo-level simulated annealing for solving certain class of hard combinatorial optimization problems. This two-level simulated annealing algorithm is less likely to get stuck at a non-global minimizer than conventional simulated annealing algorithms. We also propose a parallel version of our two-level simulated annealing algorithm and discuss its efficiency. This new technique is then applied to the Molecular Conformation problem in 3 dimensional Euclidean space. Extensive computational results on Thinking Machines CM-5 are presented. With the full Lennard-Jones potential function, we were able to get satisfactory results for problems for cluster sizes as large as 100,000. A peak rate of over 0.8 giga flop per second in 64-bit operations was sustained on a partition with 512 processing elements. To the best of our knowledge, ground states of Lennard-Jones clusters of size as large as these have never been reported before.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096722
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 20
    Electronic Resource
    Electronic Resource
    The cluster problem in multivariate global optimization (1994)
    Springer
    Journal of global optimization 5 (1994), S. 253-265 
    Details
    ISSN: 1573-2916
    Keywords: Branch and bound principle ; inclusion function ; interval extensions ; midpoint test ; global optimization ; order of an interval extension ; nonconvex optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We consider branch and bound methods for enclosing all unconstrained global minimizers of a nonconvex nonlinear twice-continuously differentiable objective function. In particular, we consider bounds obtained with interval arithmetic, with the “midpoint test,” but no acceleration procedures. Unless the lower bound is exact, the algorithm without acceleration procedures in general gives an undesirable cluster of boxes around each minimizer. In a previous paper, we analyzed this problem for univariate objective functions. In this paper, we generalize that analysis to multi-dimensional objective functions. As in the univariate case, the results show that the problem is highly related to the behavior of the objective function near the global minimizers and to the order of the corresponding interval extension.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096455
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 21
    Electronic Resource
    Electronic Resource
    Global optimization of a quadratic functional with quadratic equality constraints (1994)
    Springer
    Journal of optimization theory and applications 82 (1994), S. 379-386 
    Details
    ISSN: 1573-2878
    Keywords: Quadratic functionals ; quadratic equality constraints ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper, we investigate a constrained optimization problem with a quadratic cost functional and two quadratic equality constraints. While it is obvious that, for a nonempty constraint set, there exists a global minimum cost, a method to determine if a given local solution yields the global minimum cost has not been established. We develop a necessary and sufficient condition that will guarantee that solutions of the optimization problem yield the global minimum cost. This constrained optimization problem occurs naturally in the computation of the phase margin for multivariable control systems. Our results guarantee that numerical routines can be developed that will converge to the global solution for the phase margin.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02191860
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 22
    Electronic Resource
    Electronic Resource
    On the solution and complexity of a generalized linear complementarity problem (1994)
    Springer
    Journal of global optimization 4 (1994), S. 415-424 
    Details
    ISSN: 1573-2916
    Keywords: Complementarity problems ; polynomial complexity ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We introduce some sufficient conditions under which a generalized linear complementarity problem (GLCP) can be solved as a pure linear complementarity problem. We also establish that the GLCP is in general a NP-Hard problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01099266
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 23
    Electronic Resource
    Electronic Resource
    Optimization over the efficient set: Four special cases (1994)
    Springer
    Journal of optimization theory and applications 80 (1994), S. 3-18 
    Details
    ISSN: 1573-2878
    Keywords: Multiple criteria decision making ; efficient set ; global optimization ; linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Recently, researchers and practitioners have been increasingly interested in the problem (P) of maximizing a linear function over the efficient set of a multiple objective linear program. Problem (P) is generally a difficult global optimization problem which requires numerically intensive procedures for its solution. In this paper, simple linear programming procedures are described for detecting and solving four special cases of problem (P). When solving instances of problem (P), these procedures can be used as screening devices to detect and solve these four special cases.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02196590
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 24
    Electronic Resource
    Electronic Resource
    On the construction of test problems for concave minimization algorithms (1994)
    Springer
    Journal of global optimization 5 (1994), S. 399-402 
    Details
    ISSN: 1573-2916
    Keywords: Concave minimization ; concave quadratic minimization ; global optimization ; test problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We construct some classes of test problems of minimizing a concave or, more general, quasiconcave function over a polyhedral set. These test problems fulfil the general requirement that they have a global solution at a known point which is suitably chosen on the boundary of the feasible set.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096688
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 25
    Electronic Resource
    Electronic Resource
    A finite algorithm for solving general quadratic problems (1994)
    Springer
    Journal of global optimization 4 (1994), S. 1-16 
    Details
    ISSN: 1573-2916
    Keywords: Copositivity ; global optimization ; indefinite quadratic problems ; pseudoconvexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Here we propose a global optimization method for general, i.e. indefinite quadratic problems, which consist of maximizing a non-concave quadratic function over a polyhedron inn-dimensional Euclidean space. This algorithm is shown to be finite and exact in non-degenerate situations. The key procedure uses copositivity arguments to ensure escaping from inefficient local solutions. A similar approach is used to generate an improving feasible point, if the starting point is not the global solution, irrespective of whether or not this is a local solution. Also, definiteness properties of the quadratic objective function are irrelevant for this procedure. To increase efficiency of these methods, we employ pseudoconvexity arguments. Pseudoconvexity is related to copositivity in a way which might be helpful to check this property efficiently even beyond the scope of the cases considered here.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096531
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 26
    Electronic Resource
    Electronic Resource
    Global minimization of a generalized convex multiplicative function (1994)
    Springer
    Journal of global optimization 4 (1994), S. 47-62 
    Details
    ISSN: 1573-2916
    Keywords: Nonconvex minimization ; global optimization ; convex multiplicative function ; outer approximation method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract This paper discusses an algorithm for generalized convex multiplicative programming problems, a special class of nonconvex minimization problems in which the objective function is expressed as a sum ofp products of two convex functions. It is shown that this problem can be reduced to a concave minimization problem with only 2p variables. An outer approximation algorithm is proposed for solving the resulting problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096534
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 27
    Electronic Resource
    Electronic Resource
    Using copositivity for global optimality criteria in concave quadratic programming problems (1993)
    Springer
    Mathematical programming 62 (1993), S. 575-580 
    Details
    ISSN: 1436-4646
    Keywords: Non-convex non-linear programming ; global optimization ; second-order optimality conditions ; copositive matrices ; quadratic programming ; convex maximization problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this note we specify a necessary and sufficient condition for global optimality in concave quadratic minimization problems. Using this condition, it follows that, from the perspective of worst-case complexity of concave quadratic problems, the difference between local and global optimality conditions is not as large as in general. As an essential ingredient, we here use theε-subdifferential calculus via an approach of Hiriart-Urruty and Lemarechal (1990).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585185
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 28
    Electronic Resource
    Electronic Resource
    A new technique for generating quadratic programming test problems (1993)
    Springer
    Mathematical programming 61 (1993), S. 215-231 
    Details
    ISSN: 1436-4646
    Keywords: Test problem generation ; quadratic programming ; global optimization ; large-scale optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes a new technique for generating convex, strictly concave and indefinite (bilinear or not) quadratic programming problems. These problems have a number of properties that make them useful for test purposes. For example, strictly concave quadratic problems with their global maximum in the interior of the feasible domain and with an exponential number of local minima with distinct function values and indefinite and jointly constrained bilinear problems with nonextreme global minima, can be generated. Unlike most existing methods our construction technique does not require the solution of any subproblems or systems of equations. In addition, the authors know of no other technique for generating jointly constrained bilinear programming problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582148
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 29
    Electronic Resource
    Electronic Resource
    A generalized Dantzig—Wolfe decomposition principle for a class of nonconvex programming problems (1993)
    Springer
    Mathematical programming 62 (1993), S. 239-260 
    Details
    ISSN: 1436-4646
    Keywords: Decomposition ; price functions ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Since Dantzig—Wolfe's pioneering contribution, the decomposition approach using a pricing mechanism has been developed for a wide class of mathematical programs. For convex programs a linear space of Lagrangean multipliers is enough to define price functions. For general mathematical programs the price functions could be defined by using a subclass of nondecreasing functions. However the space of nondecreasing functions is no longer finite dimensional. In this paper we consider a specific nonconvex optimization problem min {f(x):h j (x)⩽g(x),j=1, ⋯,m, x∈X}, wheref(·),h j (·) andg(·) are finite convex functions andX is a closed convex set. We generalize optimal price functions for this problem in such a way that the parameters of generalized price functions are defined in a finite dimensional space. Combining convex duality and a nonconvex duality we can develop a decomposition method to find a globally optimal solution.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585169
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 30
    Electronic Resource
    Electronic Resource
    An efficient algorithm for finding the CSG representation of a simple polygon (1993)
    Springer
    Algorithmica 10 (1993), S. 1-23 
    Details
    ISSN: 1432-0541
    Keywords: Constructive solid geometry ; Computational geometry ; Boundary representation ; Monotone boolean formulae ; Incremental convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Modeling two-dimensional and three-dimensional objects is an important theme in computer graphics. Two main types of models are used in both cases: boundary representations, which represent the surface of an object explicitly but represent its interior only implicitly, and constructive solid geometry representations, which model a complex object, surface and interior together, as a boolean combination of simpler objects. Because neither representation is good for all applications, conversion between the two is often necessary. We consider the problem of converting boundary representations of polyhedral objects into constructive solid geometry (CSG) representations. The CSG representations for a polyhedronP are based on the half-spaces supporting the faces ofP. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practicalO(n logn) algorithm for doing this boundary-to-CSG conversion for a simple polygon ofn sides. We also prove that such nice formulae do not always exist for general polyhedra in three dimensions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01908629
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 31
    Electronic Resource
    Electronic Resource
    Geometric knapsack problems (1993)
    Springer
    Algorithmica 10 (1993), S. 399-427 
    Details
    ISSN: 1432-0541
    Keywords: Knapsack problems ; Computational geometry ; Convexity ; Dynamic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following “fence enclosure” problem: given a setS ofn points in the plane with valuesv i ≥ 0, we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the “value” of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, such as allowingS to consist of points and/or simple polygons. Other versions of the problems are obtained by restricting the total amount of fence available and also allowing the enclosure to consist of at mostM connected components. When there is an upper bound on the length of fence available, we show that the problem is NP-complete. We also provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01769706
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 32
    Electronic Resource
    Electronic Resource
    The slab dividing approach to solve the EuclideanP-Center problem (1993)
    Springer
    Algorithmica 9 (1993), S. 1-22 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; NP-completeness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Givenn demand points on the plane, the EuclideanP-Center problem is to findP supply points, such that the longest distance between each demand point and its closest supply point is minimized. The time complexity of the most efficient algorithm, up to now, isO(n 2 p−1· logn). In this paper, we present an algorithm with time complexityO(n 0(√P)).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185335
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 33
    Electronic Resource
    Electronic Resource
    Maximumk-covering of weighted transitive graphs with applications (1993)
    Springer
    Algorithmica 9 (1993), S. 84-100 
    Details
    ISSN: 1432-0541
    Keywords: Transitive graphs ; Network flow ; VLSI layout ; Computational geometry ; Integer sequences
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Consider a weighted transitive graph, where each vertex is assigned a positive weight. Given a positive integerk, the maximumk-covering problem is to findk disjoint cliques covering a set of vertices with maximum total weight. An 0(kn 2)-time algorithm to solve the problem in a transitive graph is proposed, wheren is the number of vertices. Based on the proposed algorithm the weighted version of a number of problems in VLSI layout (e.g.,k-layer topological via minimization), computational geometry (e.g., maximum multidimensionalk-chain), graph theory (e.g., maximumk-independent set in interval graphs), and sequence manipulation (e.g., maximum increasingk-subsequence) can be solved inO(kn 2), wheren is the input size.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185340
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 34
    Electronic Resource
    Electronic Resource
    Duality of constrained Voronoi diagrams and Delaunay triangulations (1993)
    Springer
    Algorithmica 9 (1993), S. 142-155 
    Details
    ISSN: 1432-0541
    Keywords: Voronoi diagram ; Delaunay triangulation ; Duality ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We introduce theconstrained Voronoi diagram of a planar straight-line graph containingn vertices or sites where the line segments of the graph are regarded as obstacles, and show that an extended version of this diagram is the dual of theconstrained Delaunay triangulation. We briefly discussO(n logn) algorithms for constructing the extended constrained Voronoi diagram.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188709
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 35
    Electronic Resource
    Electronic Resource
    Fast linear expected-time algorithms for computing maxima and convex hulls (1993)
    Springer
    Algorithmica 9 (1993), S. 168-183 
    Details
    ISSN: 1432-0541
    Keywords: Maxima ; Convex hulls ; Computational geometry ; Algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper examines the expected complexity of boundary problems on a set ofN points inK-space. We assume that the points are chosen from a probability distribution in which each component of a point is chosen independently of all other components. We present an algorithm to find the maximal points usingKN + O (N1−1/K log1/K N) expected scalar comparisons, for fixedK≥ 2. A lower bound shows that the algorithm is optimal in the leading term. We describe a simple maxima algorithm that is easy to code, and present experimental evidence that it has similar running time. For fixedK ≥ 2, an algorithm computes the convex hull of the set in 2KN + O(N1−1/K log1/KN) expected scalar comparisons. The history of the algorithms exhibits interesting interactions among consulting, algorithm design, data analysis, and mathematical analysis of algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188711
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 36
    Electronic Resource
    Electronic Resource
    A semidynamic construction of higher-order voronoi diagrams and its randomized analysis (1993)
    Springer
    Algorithmica 9 (1993), S. 329-356 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Dynamic algorithm ; Randomized complexity analysis ; Orderk Voronoi diagram
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite set ofn points in any dimension. In this paper we prove that a randomized construction of thek-Delaunay tree, and thus of all the order≤k Voronoi diagrams, can be done inO(n logn+k 3n) expected time and O(k2n) expected storage in the plane, which is asymptotically optimal for fixedk. Our algorithm extends tod-dimensional space with expected time complexityO(k ⌈(d+1)/2⌉+1 n ⌊(d+1)/2⌋) and space complexityO(k ⌈(d+1)/2⌉ n ⌊(d+1)/2⌋). The algorithm is simple and experimental results are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01228508
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 37
    Electronic Resource
    Electronic Resource
    The searching over separators strategy to solve some NP-hard problems in subexponential time (1993)
    Springer
    Algorithmica 9 (1993), S. 398-423 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; NP-hardness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we propose a new strategy for designing algorithms, called the searching over separators strategy. Suppose that we have a problem where the divide-and-conquer strategy can not be applied directly. Yet, also suppose that in an optimal solution to this problem, there exists a separator which divides the input points into two parts,A d andC d, in such a way that after solving these two subproblems withA d andC d as inputs, respectively, we can merge the respective subsolutions into an optimal solution. Let us further assume that this problem is an optimization problem. In this case our searching over separators strategy will use a separator generator to generate all possible separators. For each separator, the problem is solved by the divide-and-conquer strategy. If the separator generator is guaranteed to generate the desired separator existing in an optimal solution, our searching over separators strategy will always produce an optimal solution. The performance of our approach will critically depend upon the performance of the separator generator. It will perform well if the total number of separators generated is relatively small. We apply this approach to solve the discrete EuclideanP-median problem (DEPM), the discrete EuclideanP-center problem (DEPC), the EuclideanP-center problem (EPC), and the Euclidean traveling salesperson problem (ETSP). We propose $$O(n^{o(\sqrt P )} )$$ algorithms for the DEPM problem, the DEPC problem, and the EPC problem, and we propose an $$O(n^{o(\sqrt n )} )$$ algorithm for the ETSP problem, wheren is the number of input points.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01228511
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 38
    Electronic Resource
    Electronic Resource
    Ray shooting on triangles in 3-space (1993)
    Springer
    Algorithmica 9 (1993), S. 471-494 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray shooting on triangles ; Arrangements of hyperplanes ; 3-Space ; Plücker coordinates ; Isotopy classes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a uniform approach to problems involving lines in 3-space. This approach is based on mapping lines inR 3 into points and hyperplanes in five-dimensional projective space (Plücker space). We obtain new results on the following problems: 1. Preprocessn triangles so as to answer efficiently the query: “Given a ray, which is the first triangle hit?” (Ray- shooting problem). We discuss the ray-shooting problem for both disjoint and nondisjoint triangles. 2. Construct the intersection of two nonconvex polyhedra in an output sensitive way with asubquadratic overhead term. 3. Construct the arrangement ofn intersecting triangles in 3-space in an output-sensitive way, with asubquadratic overhead term. 4. Efficiently detect the first face hit by any ray in a set of axis-oriented polyhedra. 5. Preprocessn lines (segments) so as to answer efficiently the query “Given two lines, is it possible to move one into the other without crossing any of the initial lines (segments)?” (Isotopy problem). If the movement is possible produce an explicit representation of it.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187036
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 39
    Electronic Resource
    Electronic Resource
    Constructing strongly convex approximate hulls with inaccurate primitives (1993)
    Springer
    Algorithmica 9 (1993), S. 534-560 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Epsilon Geometry ; Approximate computations ; Robust algorithms ; Strongly convex polygons ; Convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The first half of this paper introducesEpsilon Geometry, a framework for the development of robust geometric algorithms using inaccurate primitives. Epsilon Geometry is based on a very general model of imprecise computations, which includes floating-point and rounded-integer arithmetic as special cases. The second half of the paper introduces the notion of a (−ɛ)-convex polygon, a polygon that remains convex even if its vertices are all arbitrarily displaced by a distance ofɛ of less, and proves some interesting properties of such polygons. In particular, we prove that for every point set there exists a (−ɛ)-convex polygonH such that every point is at most 4ɛ away fromH. Using the tools of Epsilon Geometry, we develop robust algorithms for testing whether a polygon is (−ɛ)-convex, for testing whether a point is inside a (−ɛ)-convex polygon, and for computing a (−ɛ)-convex approximate hull for a set of points.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190154
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 40
    Electronic Resource
    Electronic Resource
    Algorithms for projecting points to give the most uniform distribution with applications to hashing (1993)
    Springer
    Algorithmica 9 (1993), S. 572-590 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Duality transform ; Hashing ; Intersection-reporting algorithm ; Linear-space algorithm ; Plane sweep ; Projection ; Simplex range search ; Topological walk
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents several algorithms for projecting points so as to give the most uniform distribution. Givenn points in the plane and an integerb, the problem is to find an optimal angleθ ofb equally spaced parallel lines such that points are distributed most uniformly over buckets (regions bounded by two consecutive lines). An algorithm is known only in thetight case in which the two extreme lines are the supporting lines of the point set. The algorithm requiresO(bn2 logn) time and On2+bn) space to find an optimal solution. In this paper we improve the algorithm both in time and space, based on duality transformation. Two linear-space algorithms are presented. One runs in On2+K log n+bn) time, whereK is the number of intersections in the transformed plane.K is shown to beO(@#@ n2+bn@#@) based on a new counting scheme. The other algorithm is advantageous ifb 〈 √n. It performs a simplex range search in each slab to enumerate all the lines that intersectbucket lines, and runs in O(b0.610n1.695+K logn) time. It is also shown that the problem can be solved in polynomial time even in therelaxed case. Its one-dimensional analogue is especially related to the design of an optimal hash function for a static set of keys.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190156
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 41
    Electronic Resource
    Electronic Resource
    Splitting a configuration in a simplex (1993)
    Springer
    Algorithmica 9 (1993), S. 649-668 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Partition of point sets ; Assignment problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents a new method of partition, namedπ-splitting, of a point set ind-dimensional space. Given a pointG in ad-dimensional simplexT, T(G;i) is the subsimplex spanned by G and the ith facet ofT. LetS be a set ofn points inT, and letπ be a sequence of nonnegative integers π1, ..., nd+1 satisfying σ i=1 d+1 π1=n Theπ-splitter of (T, S) is a pointG inT such thatT(G;i) contains at leastπ i points ofS in its closure for everyi=1, 2, ...,d + 1. The associated dissection is the re-splitting. The existence of aπ-splitting is shown for any (T, S) andπ, and two efficient algorithms for finding such a splitting are given. One runs inO(d2n logn + d3n) time, and the other runs inO(n) time if the dimensiond can be considered as a constant. Applications of re-splitting to mesh generation, polygonal-tour generation, and a combinatorial assignment problem are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190161
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 42
    Electronic Resource
    Electronic Resource
    A generalized duality and applications (1993)
    Springer
    Journal of global optimization 3 (1993), S. 311-324 
    Details
    ISSN: 1573-2916
    Keywords: Nonconvex duality ; zero gap ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The aim of this paper is to present a nonconvex duality with a zero gap and its connection with convex duality. Since a convex program can be regarded as a particular case of convex maximization over a convex set, a nonconvex duality can be regarded as a generalization of convex duality. The generalized duality can be obtained on the basis of convex duality and minimax theorems. The duality with a zero gap can be extended to a more general nonconvex problems such as a quasiconvex maximization over a general nonconvex set or a general minimization over the complement of a convex set. Several applications are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096773
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 43
    Electronic Resource
    Electronic Resource
    Test case generators and computational results for the maximum clique problem (1993)
    Springer
    Journal of global optimization 3 (1993), S. 463-482 
    Details
    ISSN: 1573-2916
    Keywords: Maximum clique problem ; testing ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In the last years many algorithms have been proposed for solving the maximum clique problem. Most of these algorithms have been tested on randomly generated graphs. In this paper we present different test problem generators that arise from a variety of practical applications, as well as graphs with known maximum cliques. In addition, we provide computational experience with two exact algorithms using the generated test problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096415
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 44
    Electronic Resource
    Electronic Resource
    Necessary conditions for nonlinear suboptimization over the weakly-efficient set (1993)
    Springer
    Journal of optimization theory and applications 78 (1993), S. 579-598 
    Details
    ISSN: 1573-2878
    Keywords: Multi-objective optimization ; global optimization ; nonlinear programming ; nonconvex programming ; stability ; sensitivity analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The optimization problem of a nonlinear real function over the weakly-efficient set associated to a nonlinear multi-objective program is examined. Necessary first-order conditions for a suboptimal solution are proposed, assuming the convexity of the multi-objective program. Estimations of the optimal value are established and an algorithm for finding suboptimal solutions is proposed. The optimal value is approximated to any prescribed degree of accuracy using a weakly-efficient suboptimal solution.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00939883
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 45
    Electronic Resource
    Electronic Resource
    An outer approximation method for minimizing the product of several convex functions on a convex set (1993)
    Springer
    Journal of global optimization 3 (1993), S. 325-335 
    Details
    ISSN: 1573-2916
    Keywords: Nonconvex minimization ; global optimization ; outer approximation method ; convex multiplicative function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract This paper addresses the minimization of the product ofp convex functions on a convex set. It is shown that this nonconvex problem can be converted to a concave minimization problem withp variables, whose objective function value is determined by solving a convex minimization problem. An outer approximation method is proposed for obtaining a global minimum of the resulting problem. Computational experiments indicate that this algorithm is reasonable efficient whenp is less than 4.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096774
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 46
    Electronic Resource
    Electronic Resource
    A global optimization approach for the linear two-level program (1993)
    Springer
    Journal of global optimization 3 (1993), S. 1-23 
    Details
    ISSN: 1573-2916
    Keywords: Linear two-level program ; global optimization ; Stackelberg game ; reverse convex constraint programming ; polyhedral annexation method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Linear two-level programming deals with optimization problems in which the constraint region is implicity determined by another optimization problem. Mathematical programs of this type arise in connection with policy problems to which the Stackelberg leader-follower game is applicable. In this paper, the linear two-level programming problem is restated as a global optimization problem and a new solution method based on this approach is developed. The most important feature of this new method is that it attempts to take full advantage of the structure in the constraints using some recent global optimization techniques. A small example is solved in order to illustrate the approach.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01100237
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 47
    Electronic Resource
    Electronic Resource
    Globally convergent algorithm for solving nonlinear equations (1993)
    Springer
    Journal of optimization theory and applications 77 (1993), S. 291-304 
    Details
    ISSN: 1573-2878
    Keywords: Nonlinear equations ; global optimization ; global convergence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A general iterative method is proposed for finding the maximal rootx max of a one-variable equation in a given interval. The method generates a monotone-decreasing sequence of points converging tox max or demonstrates the nonexistence of a real root. It is globally convergent. A concrete realization of the general algorithm is also given and is shown to be locally quadratically convergent. Computational experience obtained for eight test problems indicates that the new method is comparable to known methods claiming global convergence.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00940713
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 48
    Electronic Resource
    Electronic Resource
    Improving Hit-and-Run for global optimization (1993)
    Springer
    Journal of global optimization 3 (1993), S. 171-192 
    Details
    ISSN: 1573-2916
    Keywords: Random search ; Monte Carlo optimization ; algorithm complexity ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Improving Hit-and-Run is a random search algorithm for global optimization that at each iteration generates a candidate point for improvement that is uniformly distributed along a randomly chosen direction within the feasible region. The candidate point is accepted as the next iterate if it offers an improvement over the current iterate. We show that for positive definite quadratic programs, the expected number of function evaluations needed to arbitrarily well approximate the optimal solution is at most O(n5/2) wheren is the dimension of the problem. Improving Hit-and-Run when applied to global optimization problems can therefore be expected to converge polynomially fast as it approaches the global optimum.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096737
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 49
    Electronic Resource
    Electronic Resource
    On the global optimization properties of finite-difference local descent algorithms (1993)
    Springer
    Journal of global optimization 3 (1993), S. 67-78 
    Details
    ISSN: 1573-2916
    Keywords: Gradient method ; coordinate descent method ; global optimization ; stability under perturbations
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The paper is devoted to the convergence properties of finite-difference local descent algorithms in global optimization problems with a special γ-convex structure. It is assumed that the objective function can be closely approximated by some smooth convex function. Stability properties of the perturbed gradient descent and coordinate descent methods are investigated. Basing on this results some global optimization properties of finite-difference local descent algorithms, in particular, coordinate descent method, are discovered. These properties are not inherent in methods using exact gradients.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01100240
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 50
    Electronic Resource
    Electronic Resource
    Customizing methods for global optimization-a geometric viewpoint (1993)
    Springer
    Journal of global optimization 3 (1993), S. 193-212 
    Details
    ISSN: 1573-2916
    Keywords: Multidimensional bisection ; deterministic ; global optimization ; mathematical programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A new class of global optimization algorithms, extending the multidimensional bisection method of Wood, is described geometrically. New results show how the geometry of the global minimum relates to performance. Remarkably, the epigraph of the objective function, turned upside down, plays a key role. Algorithms customized to take advantage of special information about the objective function belong to the class. A number of algorithms in the literature, including those of Piyavskii-Shubert, Mladineo, Wood and Breiman & Cutler, also belong, and simple modifications of them produce customized algorithms. Comparison of various algorithms in the class is provided.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096738
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 51
    Electronic Resource
    Electronic Resource
    Pure adaptive search in global optimization (1992)
    Springer
    Mathematical programming 53 (1992), S. 323-338 
    Details
    ISSN: 1436-4646
    Keywords: Random search ; Monte Carlo optimization ; global optimization ; complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Pure adaptive seach iteratively constructs a sequence of interior points uniformly distributed within the corresponding sequence of nested improving regions of the feasible space. That is, at any iteration, the next point in the sequence is uniformly distributed over the region of feasible space containing all points that are strictly superior in value to the previous points in the sequence. The complexity of this algorithm is measured by the expected number of iterations required to achieve a given accuracy of solution. We show that for global mathematical programs satisfying the Lipschitz condition, its complexity increases at mostlinearly in the dimension of the problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585710
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 52
    Electronic Resource
    Electronic Resource
    Linear multiplicative programming (1992)
    Springer
    Mathematical programming 56 (1992), S. 51-64 
    Details
    ISSN: 1436-4646
    Keywords: Non-convex quadratic programming problem ; global optimization ; parametric simplex algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An algorithm for solving a linear multiplicative programming problem (referred to as LMP) is proposed. LMP minimizes the product of two linear functions subject to general linear constraints. The product of two linear functions is a typical non-convex function, so that it can have multiple local minima. It is shown, however, that LMP can be solved efficiently by the combination of the parametric simplex method and any standard convex minimization procedure. The computational results indicate that the amount of computation is not much different from that of solving linear programs of the same size. In addition, the method proposed for LMP can be extended to a convex multiplicative programming problem (CMP), which minimizes the product of two convex functions under convex constraints.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580893
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 53
    Electronic Resource
    Electronic Resource
    Deciding uniqueness in norm maximization (1992)
    Springer
    Mathematical programming 57 (1992), S. 203-214 
    Details
    ISSN: 1436-4646
    Keywords: 90C30 ; 68Q15 ; 90C20 ; 90C25 ; 52A25 ; global optimization ; quadratic programming ; unique optimum ; polytope ; parallelotope ; norm ; NP-hardness ; diameter ; width ; inradius ; circumradius
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract NP-hardness is established for the problem whose instance is a system of linear inequalities defining a polytopeP, and whose question is whether, onP, the global maximum of the Euclidean norm is attained at more than one vertex ofP. The NP-hardness persists even for the restricted problem in whichP is a full-dimensional parallelotope with one vertex at the origin. This makes it possible to establish NP-hardness for other uniqueness problems, including some from pseudoboolean programming and computational convexity.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581081
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 54
    Electronic Resource
    Electronic Resource
    A decomposition method using a pricing mechanism for min concave cost flow problems with a hierarchical structure (1992)
    Springer
    Mathematical programming 53 (1992), S. 339-359 
    Details
    ISSN: 1436-4646
    Keywords: Concave cost ; hierarchical structure ; uncapacitated network ; nonconvex decomposition ; pricing mechanism ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we develop a decomposition method using a pricing mechanism which has been widely applied to linear and convex programs for a class of nonconvex optimization problems that are min concave cost flow problems under directed, uncapacitated networks with a hierarchical structure.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585711
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 55
    Electronic Resource
    Electronic Resource
    Optimal randomized parallel algorithms for computational geometry (1992)
    Springer
    Algorithmica 7 (1992), S. 91-117 
    Details
    ISSN: 1432-0541
    Keywords: Randomized ; Parallel algorithm ; Computational geometry ; Point location ; Triangulation ; Trapezoidal decomposition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present parallel algorithms for some fundamental problems in computational geometry which have a running time ofO(logn) usingn processors, with very high probability (approaching 1 asn → ∞). These include planar-point location, triangulation, and trapezoidal decomposition. We also present optimal algorithms for three-dimensional maxima and two-set dominance counting by an application of integer sorting. Most of these algorithms run on a CREW PRAM model and have optimal processor-time product which improve on the previously best-known algorithms of Atallah and Goodrich [5] for these problems. The crux of these algorithms is a useful data structure which emulates the plane-sweeping paradigm used for sequential algorithms. We extend some of the techniques used by Reischuk [26] and Reif and Valiant [25] for flashsort algorithm to perform divide and conquer in a plane very efficiently leading to the improved performance by our approach.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758753
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 56
    Electronic Resource
    Electronic Resource
    Optimal parallel algorithms for point-set and polygon problems (1992)
    Springer
    Algorithmica 7 (1992), S. 3-23 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Parallel algorithms ; Polygon ; All nearest-neighbor problem ; Kernel problem ; Convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimalT(n) * P(n) products, whereT(n) is the time complexity andP(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758749
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 57
    Electronic Resource
    Electronic Resource
    Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers (1992)
    Springer
    Algorithmica 7 (1992), S. 51-75 
    Details
    ISSN: 1432-0541
    Keywords: Hypercube ; Parallel algorithms ; Convex hull ; Domination ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper gives hypercube algorithms for some simple problems involving geometric properties of sets of points. The properties considered emphasize aspects of convexity and domination. Efficient algorithms are given for both fine- and medium-grain hypercube computers, including a discussion of implementation, running times and results on an Intel iPSC hypercube, as well as theoretical results. For both serial and parallel computers, sorting plays an important role in geometric algorithms for determining simple properties, often being the dominant component of the running time. Since the time required to sort data on a hypercube computer is still not fully understood, the running times of some of our algorithms for unsorted data are not completely determined. For both the fine- and medium-grain models, we show that faster expected-case running time algorithms are possible for point sets generated randomly. Our algorithms are developed for sets of planar points, with several of them extending to sets of points in spaces of higher dimension.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758751
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 58
    Electronic Resource
    Electronic Resource
    L 1 shortest paths among polygonal obstacles in the plane (1992)
    Springer
    Algorithmica 8 (1992), S. 55-88 
    Details
    ISSN: 1432-0541
    Keywords: Shortest paths ; Voronoi diagrams ; Rectilinear paths ; Wire routing ; Fixed orientation metrics ; Continuous Dijkstra algorithm ; Computational geometry ; Extremal graph theory
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an algorithm for computingL 1 shortest paths among polygonal obstacles in the plane. Our algorithm employs the “continuous Dijkstra” technique of propagating a “wavefront” and runs in timeO(E logn) and spaceO(E), wheren is the number of vertices of the obstacles andE is the number of “events.” By using bounds on the density of certain sparse binary matrices, we show thatE =O(n logn), implying that our algorithm is nearly optimal. We conjecture thatE =O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space. Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(nɛ−1/2 log2 n) time andO(nɛ−1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL 1 Voronoi diagram for source points that lie among a collection of polygonal obstacles.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758836
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 59
    Electronic Resource
    Electronic Resource
    Line-segment intersection reporting in parallel (1992)
    Springer
    Algorithmica 8 (1992), S. 119-144 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Line-segment intersection reporting ; Segment tree ; PRAM
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give a parallel algorithm for line-segment intersection reporting in the plane. It runs in timeO(((n +k) logn log logn)/p) usingp processors on a concurrent-read-exclusive-write (CREW)-PRAM, wheren is the number of line segments,k is the number of intersections, andp ≤n +k.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758839
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 60
    Electronic Resource
    Electronic Resource
    An efficient algorithm for one-step planar compliant motion planning with uncertainty (1992)
    Springer
    Algorithmica 8 (1992), S. 195-208 
    Details
    ISSN: 1432-0541
    Keywords: Motion planning ; Compliant motion ; Uncertainty ; Robotics ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Uncertainty in the execution of robot motion plans must be accounted for in the geometric computations from which plans are obtained, especially in the case where position sensing is inaccurate. We give anO(n 2 logn) algorithm to find a single commanded motion direction that will guarantee a successful motion in the plane from a specified start to a specified goal whenever such a one-step motion is possible. The plans account for uncertainty in the start position and in robot control, and anticipate that the robot may stick on or slide along obstacle surfaces with which it comes in contact. This bound improves on the best previous bound by a quadratic factor, and is achieved in part by a new analysis of the geometric complexity of the backprojection of the goal as a function of commanded motion direction.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758843
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 61
    Electronic Resource
    Electronic Resource
    Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs (1992)
    Springer
    Algorithmica 8 (1992), S. 177-194 
    Details
    ISSN: 1432-0541
    Keywords: Matching ; Computational geometry ; Bottleneck optimization problem ; Relative neighborhood graph
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a set of pointsV in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,E r k ) whereE r k is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofE r 17 . We also prove that ¦E r k ¦ 〈 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n 2) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)0.5 m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n 1.5 log0.5 n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n 2 +n 1.5 log0.5 n).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758842
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 62
    Electronic Resource
    Electronic Resource
    On the parallel-decomposability of geometric problems (1992)
    Springer
    Algorithmica 8 (1992), S. 209-231 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Mesh-connected arrays of processors ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract There is a large and growing body of literature concerning the solutions of geometric problems on mesh-connected arrays of processors. Most of these algorithms are optimal (i.e., run in timeO(n 1/d ) on ad-dimensionaln-processor array), and they all assume that the parallel machine is trying to solve a problem of sizen on ann-processor array. Here we investigate the situation where we have a mesh of sizep and we are interested in using it to solve a problem of sizen 〉p. The goal we seek is to achieve, when solving a problem of sizen 〉p, the same speed up as when solving a problem of sizep. We show that for many geometric problems, the same speedup can be achieved when solving a problem of sizen 〉p as when solving a problem of sizep.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758844
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 63
    Electronic Resource
    Electronic Resource
    Output-sensitive generation of the perspective view of isothetic parallelepipeds (1992)
    Springer
    Algorithmica 8 (1992), S. 257-283 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Hidden-line elimination ; Perspective view ; Isothetic rectangles ; Parallelepipeds ; Fractional cascading ; Segment tree ; Range tree ; Dominance relation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a new hidden-line elemination technique for displaying the perspective view of a scene of three-dimensional isothetic parallelepipeds (3D-rectangles). We assume that the 3D-rectangles are totally ordered based upon the dominance relation of occlusion. The perspective view is generated incrementally, starting with the closest 3D-rectangle and proceeding away from the view point. Our algorithm is scene-sensitive and uses0((n +d) logn log logn) time, wheren is the number of 3D-rectangles andd is the number of edges of the display. This improves over the heretofore best known technique. The primary data structure is an efficient alternative to dynamic fractional cascading for use with augmented segment and range trees when the universe is fixed beforehand. It supports queries inO((logn +k) log logn) time, wherek is the size of the response, and insertions and deletions inO(logn log logn) time, all in the worst case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758847
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 64
    Electronic Resource
    Electronic Resource
    Probing a scene of nonconvex polyhedra (1992)
    Springer
    Algorithmica 8 (1992), S. 321-342 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Geometric probing ; Polyhedral scenes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show, in this paper, how the exact shapes of a class of polyhedral scenes can be computed by means of a simple sensory device issuing probes. A scene in this class consists of disjoint polyhedra with no collinear edges, no coplanar faces, and such that no edge is contained in the supporting plane of a nonincident face. The basic step of our method is a strategy for probing a single simple polygon with no collinear edges. When each probe outcome consists of a contact point and the normal to the object at the point, we present a strategy that allows us to compute the exact shape of a simple polygon with no collinear edges by means of at most3n — 3 probes, wheren is the number of edges of the polygon. This is optimal in the worst case. This strategy can be extended to probe a family of disjoint polygons. It can also be applied in planar sections of a scene of polyhedra of the class above to find out, in turn, each edge of the scene. If the scene consists ofk polyhedra with altogethern faces andm edges, we show that $$\tfrac{{10}}{3}n\left( {m + k} \right) - 2m - 3k$$ probes are sufficient to compute the exact shapes of the polyhedra.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758849
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 65
    Electronic Resource
    Electronic Resource
    Quasi-optimal upper bounds for simplex range searching and new zone theorems (1992)
    Springer
    Algorithmica 8 (1992), S. 407-429 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Range searching ; Space-time tradeoff
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ℜd so that, given any query simplexq, the points inP ∩q can be counted or reported efficiently. Ifm units of storage are available (n 〈m 〈n d ), then we show that it is possible to answer any query inO(n 1+ɛ/m 1/d ) query time afterO(m 1+ɛ) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n d+ɛ) storage for any fixed ɛ 〉 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758854
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 66
    Electronic Resource
    Electronic Resource
    Simultaneous inner and outer approximation of shapes (1992)
    Springer
    Algorithmica 8 (1992), S. 365-389 
    Details
    ISSN: 1432-0541
    Keywords: Polygonal approximation ; Algorithmic paradigms ; Shape approximation ; Computational geometry ; Implicit complexity parameters ; Banach-Mazur metric
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract For compact Euclidean bodiesP, Q, we define λ(P, Q) to be the smallest ratior/s wherer 〉 0,s 〉 0 satisfy $$sQ' \subseteq P \subseteq rQ''$$ . HeresQ denotes a scaling ofQ by the factors, andQ′,Q″ are some translates ofQ. This function λ gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.) For integerk ≥ 3, define λ(k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with λ(P, Q) ≤ λ(k). Among other results, we prove that 2.118 ... 〈-λ(3) ≤ 2.25 and λ(k) = 1 + Θ(k −2). We give anO(n 2 log2 n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes λ(T, P) among triangles. However, in linear time we can find a trianglet with λ(t, P)〈-2.25. Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758852
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 67
    Electronic Resource
    Electronic Resource
    Approximate motion planning and the complexity of the boundary of the union of simple geometric figures (1992)
    Springer
    Algorithmica 8 (1992), S. 391-406 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Motion planning ; Boundary complexity ; Combinatorial geometry ; Analysis of algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have a running time of Ω(n 2), wheren is the number of obstacle corners. We introduce thetightness of a motion-planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with a running time ofO((a/b · 1/ɛcrit + 1)n(logn)2), wherea ≥b are the lengths of the sides of a rectangle and ɛcrit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary ofn bow ties (see Figure 1) isO(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758853
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 68
    Electronic Resource
    Electronic Resource
    Minimum-link paths among obstacles in the plane (1992)
    Springer
    Algorithmica 8 (1992), S. 431-459 
    Details
    ISSN: 1432-0541
    Keywords: Link distance ; Shortest paths ; Motion planning ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a set of nonintersecting polygonal obstacles in the plane, thelink distance between two pointss andt is the minimum number of edges required to form a polygonal path connectings tot that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in timeO(Eα(n) log2 n) (and spaceO(E)), wheren is the total number of edges of the obstacles,E is the size of the visibility graph, and α(n) denotes the extremely slowly growing inverse of Ackermann's function. We show how to extend our method to allow computation of a tree (rooted ats) of minimum-link paths froms to all obstacle vertices. This leads to a method of solving the query version of our problem (for query pointst).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758855
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 69
    Electronic Resource
    Electronic Resource
    Parallel methods for visibility and shortest-path problems in simple polygons (1992)
    Springer
    Algorithmica 8 (1992), S. 461-486 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Data structures ; Visibility ; Polygons ; CREW PRAM
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give efficient parallel algorithms for solving a number of visibility and shortest-path problems for simple polygons. Our algorithms all run inO(logn) time and are based on the use of a new data structure for implicitly representing all shortest paths in a simple polygonP, which we call thestratified decomposition tree. We use this approach to derive efficient parallel methods for computing the visibility ofP from an edge, constructing the visibility graph of the vertices ofP (using an output-sensitive number of processors), constructing the shortest-path tree from a vertex ofP, and determining all-farthest neighbors for the vertices inP. The computational model we use is the CREW PRAM.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758856
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 70
    Electronic Resource
    Electronic Resource
    Reduction of indefinite quadratic programs to bilinear programs (1992)
    Springer
    Journal of global optimization 2 (1992), S. 41-60 
    Details
    ISSN: 1573-2916
    Keywords: Quadratic program ; bilinear program ; global optimization ; reduction
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Indefinite quadratic programs with quadratic constraints can be reduced to bilinear programs with bilinear constraints by duplication of variables. Such reductions are studied in which: (i) the number of additional variables is minimum or (ii) the number of complicating variables, i.e., variables to be fixed in order to obtain a linear program, in the resulting bilinear program is minimum. These two problems are shown to be equivalent to a maximum bipartite subgraph and a maximum stable set problem respectively in a graph associated with the quadratic program. Non-polynomial but practically efficient algorithms for both reductions are thus obtaine.d Reduction of more general global optimization problems than quadratic programs to bilinear programs is also briefly discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00121301
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 71
    Electronic Resource
    Electronic Resource
    A finite, nonadjacent extreme-point search algorithm for optimization over the efficient set (1992)
    Springer
    Journal of optimization theory and applications 73 (1992), S. 47-64 
    Details
    ISSN: 1573-2878
    Keywords: Multiple-criteria decision making ; extreme-point search ; global optimization ; efficient set ; nonconvex programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The problem (P) of optimizing a linear function over the efficient set of a multiple-objective linear program serves many useful purposes in multiple-criteria decision making. Mathematically, problem (P) can be classified as a global optimization problem. Such problems are much more difficult to solve than convex programming problems. In this paper, a nonadjacent extreme-point search algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact extreme-point optimal solution for the problem after a finite number of iterations. It can be implemented using only linear programming methods. Convergence of the algorithm is proven, and a discussion is included of its main advantages and disadvantages.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00940077
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 72
    Electronic Resource
    Electronic Resource
    An interval branch and bound algorithm for bound constrained optimization problems (1992)
    Springer
    Journal of global optimization 2 (1992), S. 259-280 
    Details
    ISSN: 1573-2916
    Keywords: Primary: 65K10 ; Secondary: 65G10 ; Nonlinear algebraic systems ; Newton's method ; interval arithmetic ; Gauss-Seidel method ; global optimization ; singularities
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper, we propose modifications to a prototypical branch and bound algorithm for nonlinear optimization so that the algorithm efficiently handles constrained problems with constant bound constraints. The modifications involve treating subregions of the boundary identically to interior regions during the branch and bound process, but using reduced gradients for the interval Newton method. The modifications also involve preconditioners for the interval Gauss-Seidel method which are optimal in the sense that their application selectively gives a coordinate bound of minimum width, a coordinate bound whose left endpoint is as large as possible, or a coordinate bound whose right endpoint is as small as possible. We give experimental results on a selection of problems with different properties.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00171829
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 73
    Electronic Resource
    Electronic Resource
    Global optimization approach to nonlinear optimal control (1992)
    Springer
    Journal of optimization theory and applications 73 (1992), S. 547-562 
    Details
    ISSN: 1573-2878
    Keywords: Nonlinear optimal control ; nonlinear programming ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract To determine the optimum in nonlinear optimal control problems, it is proposed to convert the continuous problems into a form suitable for nonlinear programming (NLP). Since the resulting finite-dimensional NLP problems can present multiple local optima, a global optimization approach is developed where random starting conditions are improved by using special line searches. The efficiency, speed, and reliability of the proposed approach is examined by using two examples.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00940055
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 74
    Electronic Resource
    Electronic Resource
    Global optimization by multilevel search (1992)
    Springer
    Journal of optimization theory and applications 75 (1992), S. 423-432 
    Details
    ISSN: 1573-2878
    Keywords: Multilevel methods ; global optimization ; Monte Carlo methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A new approach to the global optimization of functions with extremely rugged graphs is introduced. This multilevel search method is both an algorithm and a meta-algorithm, a logic for regulating optimization done by other algorithms. First, it is examined in the one-dimensional case theoretically and through simple examples. Then, to deal with higher dimensions, multilevel search is combined with the Monte Carlo method; this hybrid algorithm is tested on standard problems and is found to perform extremely well for a derivative-free method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00941477
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 75
    Electronic Resource
    Electronic Resource
    Application of the renormalization group to deterministic global minimization of molecular conformation energy functions (1992)
    Springer
    Journal of global optimization 2 (1992), S. 281-311 
    Details
    ISSN: 1573-2916
    Keywords: Renormalization group ; global optimization ; conformation ; microcluster ; annealing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We outline a new global minimization method in which the Gibbs distribution of the objective function is deterministically annealed by tracing the evolution of a multiple-Gaussian-packet approximation. Solutions are reached by iterative approximations with decreasing coarse-graining of both objective-function and spatial scales. Results from application of a partial implementation to the atomic-microcluster conformation problem are presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00171830
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 76
    Electronic Resource
    Electronic Resource
    A new reformulation-linearization technique for bilinear programming problems (1992)
    Springer
    Journal of global optimization 2 (1992), S. 379-410 
    Details
    ISSN: 1573-2916
    Keywords: Bilinear programming ; nonconvex programming ; global optimization ; branch-and-bound ; reformulation-linearization technique
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract This paper is concerned with the development of an algorithm for general bilinear programming problems. Such problems find numerous applications in economics and game theory, location theory, nonlinear multi-commodity network flows, dynamic assignment and production, and various risk management problems. The proposed approach develops a new Reformulation-Linearization Technique (RLT) for this problem, and imbeds it within a provably convergent branch-and-bound algorithm. The method first reformulates the problem by constructing a set of nonnegative variable factors using the problem constraints, and suitably multiplies combinations of these factors with the original problem constraints to generate additional valid nonlinear constraints. The resulting nonlinear program is subsequently linearized by defining a new set of variables, one for each nonlinear term. This “RLT” process yields a linear programming problem whose optimal value provides a tight lower bound on the optimal value to the bilinear programming problem. Various implementation schemes and constraint generation procedures are investigated for the purpose of further tightening the resulting linearization. The lower bound thus produced theoretically dominates, and practically is far tighter, than that obtained by using convex envelopes over hyper-rectangles. In fact, for some special cases, this process is shown to yield an exact linear programming representation. For the associated branch-and-bound algorithm, various admissible branching schemes are discussed, including one in which branching is performed by partitioning the intervals for only one set of variables x or y, whichever are fewer in number. Computational experience is provided to demonstrate the viability of the algorithm. For a large number of test problems from the literature, the initial bounding linear program itself solves the underlying bilinear programming problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00122429
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 77
    Electronic Resource
    Electronic Resource
    The complementary convex structure in global optimization (1992)
    Springer
    Journal of global optimization 2 (1992), S. 21-40 
    Details
    ISSN: 1573-2916
    Keywords: Complementary convex structure ; Generalized Rank k Property ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We show the importance of exploiting the complementary convex structure for efficiently solving a wide class of specially structured nonconvex global optimization problems. Roughly speaking, a specific feature of these problems is that their nonconvex nucleus can be transformed into a complementary convex structure which can then be shifted to a subspace of much lower dimension than the original underlying space. This approach leads to quite efficient algorithms for many problems of practical interest, including linear and convex multiplicative programming problems, concave minimization problems with few nonlinear variables, bilevel linear optimization problems, etc...
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00121300
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 78
    Electronic Resource
    Electronic Resource
    Optimal decomposition of probabilistic networks by simulated annealing (1992)
    Springer
    Statistics and computing 2 (1992), S. 7-17 
    Details
    ISSN: 1573-1375
    Keywords: Simulated annealing ; global optimization ; Monte Carlo algorithms ; graph decomposition ; probabilistic networks ; NP-complete problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper investigates the applicability of a Monte Carlo technique known as ‘simulated annealing’ to achieve optimum or sub-optimum decompositions of probabilistic networks under bounded resources. High-quality decompositions are essential for performing efficient inference in probabilistic networks. Optimum decomposition of probabilistic networks is known to be NP-hard (Wen, 1990). The paper proves that cost-function changes can be computed locally, which is essential to the efficiency of the annealing algorithm. Pragmatic control schedules which reduce the running time of the annealing algorithm are presented and evaluated. Apart from the conventional temperature parameter, these schedules involve the radius of the search space as a new control parameter. The evaluation suggests that the inclusion of this new parameter is important for the success of the annealing algorithm for the present problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01890544
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 79
    Electronic Resource
    Electronic Resource
    Concave minimization via conical partitions and polyhedral outer approximation (1991)
    Springer
    Mathematical programming 50 (1991), S. 259-274 
    Details
    ISSN: 1436-4646
    Keywords: Concave minimization ; global optimization ; nonlinear programming ; nonconvex programming ; branch-and-bound ; outer approximation ; cutting planes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An algorithm is proposed for globally minimizing a concave function over a compact convex set. This algorithm combines typical branch-and-bound elements like partitioning, bounding and deletion with suitably introduced cuts in such a way that the computationally most expensive subroutines of previous methods are avoided. In each step, essentially only few linear programming problems have to be solved. Some preliminary computational results are reported.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01594938
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 80
    Electronic Resource
    Electronic Resource
    A tight upper bound for the number of intersections between two rectangular paths (1991)
    Springer
    BIT 31 (1991), S. 598-606 
    Details
    ISSN: 1572-9125
    Keywords: B.7.1 ; B.7.2 ; F.2.2 ; G.2.2 ; Computational geometry ; interference ; intersection ; rectangular path ; upper bound ; VLSI layout
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The problem of finding the number of intersections between two geometric figures in the plane has been studied extensively in literature. In this paper, the geometric figure comprising a continuous rectilinear path (called rectangular path) is considered, and a tight (least) upper bound onI(P, Q), the number of intersections between two rectangular pathsP andQ, is given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01933175
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 81
    Electronic Resource
    Electronic Resource
    Probabilistic analysis of an algorithm for solving thek-dimensional all-nearest-neighbors problem by projection (1991)
    Springer
    BIT 31 (1991), S. 558-565 
    Details
    ISSN: 1572-9125
    Keywords: F.2.2 ; Computational geometry ; plane-sweep algorithm ; proximity problems ; all-nearest-neighbor problem ; probabilistic analysis of algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A well-known simple heuristic algorithm for solving the all-nearest-neighbors problem in thek-dimensional Euclidean spaceE k ,k〉1, projects the given point setS onto thex-axis. For each pointq εS a nearest neighbor inS under anyL p -metric (1 ≤p ≤ ∞) is found by sweeping fromq into two opposite directions along thex-axis. If δ q denotes the distance betweenq and its nearest neighbor inS the sweep process stops after all points in a vertical 2δ q -slice centered aroundq have been examined. We show that this algorithm solves the all-nearest-neighbors problem forn independent and uniformly distributed points in the unit cube [0,1] k in Θ(n 2−1/k ) expected time, while its worst-case performance is Θ(n 2).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01933171
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 82
    Electronic Resource
    Electronic Resource
    Finding minimal nested polygons (1991)
    Springer
    BIT 31 (1991), S. 230-236 
    Details
    ISSN: 1572-9125
    Keywords: F.1.2 ; Algorithm ; Complexity ; Computational geometry ; Minimal nested polygon
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract An algorithm for finding a polygon with minimum number of edges nested in two simplen-sided polygons is presented. The algorithm solves the problem in at mostO(n logn) time, and improves the time complexity of two previousO(n 2) algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01931283
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 83
    Electronic Resource
    Electronic Resource
    Moving a disc between polygons (1991)
    Springer
    Algorithmica 6 (1991), S. 182-191 
    Details
    ISSN: 1432-0541
    Keywords: Motion planning ; Polygonal obstacles ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An algorithm is given for finding a collision-free path for a disc between a collection of polygons havingn corners in total. The polygons are fixed and can be preprocessed. A query specifies the radiusr of the disc to be moved and the start and destination points of the center of the disc. The answer whether a feasible path exists is given in timeO(logn). Returning a feasible path is done in additional time proportional to the length of the description of the path. Preprocessing time isO(n logn) and space complexity isO(n).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759040
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 84
    Electronic Resource
    Electronic Resource
    AnO(n logn) plane-sweep algorithm forL 1 andL ∞ Delaunay triangulations (1991)
    Springer
    Algorithmica 6 (1991), S. 207-221 
    Details
    ISSN: 1432-0541
    Keywords: Delaunay triangulation ; Plane-sweep algorithm ; Voronoi diagram ; L 1 metric ; L ∞ metric ; Computational geometry ; Minimal spanning tree
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract TheDelaunay diagram on a set of points in the plane, calledsites, is the straight-line dual graph of the Voronoi diagram. When no degeneracies are present, the Delaunay diagram is a triangulation of the sites, called theDelaunay triangulation. When degeneracies are present, edges must be added to the Delaunay diagram to obtain a Delaunay triangulation. In this paper we describe an optimalO(n logn) plane-sweep algorithm for computing a Delaunay triangulation on a possibly degenerate set of sites in the plane under theL 1 metric or theL ∞ metric.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759042
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 85
    Electronic Resource
    Electronic Resource
    Order-k voronoi diagrams of sites with additive weights in the plane (1991)
    Springer
    Algorithmica 6 (1991), S. 490-521 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Voronoi diagrams ; Geömetric transformation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract It is shown that the order-k Voronoi diagram of n sites with additive weights in the plane has at most (4k−2)(n−k) vertices, (6k−3)(n−k) edges, and (2k−1)(n−itk) + 1 regions. These bounds are approximately the same as the ones known for unweighted order-k Voronoi diagrams. Furthermore, tight upper bounds on the number of edges and vertices are given for the case that every weighted site has a nonempty region in the order-1 diagram. The proof is based on a new algorithm for the construction of these diagrams which generalizes a plane-sweep algorithm for order-1 diagrams developed by Steven Fortune. The new algorithm has time-complexityO(k 2 n logn) and space-complexityO(kn). It is the only nontrivial algorithm known for constructing order-kc Voronoi diagrams of sites withadditive weights. It is fairly simple and of practical interest also in the special case of unweighted sites.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759056
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 86
    Electronic Resource
    Electronic Resource
    Convex hulls of objects bounded by algebraic curves (1991)
    Springer
    Algorithmica 6 (1991), S. 533-553 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Algorithms and data structures ; Algebraic geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an0(n ·d o(1)) algorithm to compute the convex hull of a curved object bounded by0(n) algebraic curve segments of maximum degreed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759058
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 87
    Electronic Resource
    Electronic Resource
    Finding a minimal cover for binary images: An optimal parallel algorithm (1991)
    Springer
    Algorithmica 6 (1991), S. 624-657 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Image compression ; Minimal square covers ; Orthogonal polygons ; Parallel prefix computations ; Minimal vertex covers ; Bipartite graphs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a black-and-white image, represented by an array of √n × √n binary-valued pixels, we wish to cover the black pixels with aminimal set of (possibly overlapping) maximal squares. It was recently shown that obtaining aminimum square cover for a polygonal binary image with holes is NP-hard. We derive an optimal parallel algorithm for theminimal square cover problem, which for any desired computation timeT in [logn,n] runs on an EREW-PRAM with (n/T) processors. The cornerstone of our algorithm is a novel data structure, the cover graph, which compactly represents the covering relationships between the maximal squares of the image. The size of the cover graph is linear in the number of pixels. This algorithm has applications to problems in VLSI mask generation, incremental update of raster displays, and image compression.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759065
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 88
    Electronic Resource
    Electronic Resource
    On partitioning rectilinear polygons into star-shaped polygons (1991)
    Springer
    Algorithmica 6 (1991), S. 771-800 
    Details
    ISSN: 1432-0541
    Keywords: Polygon decomposition ; Star-shaped polygons ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an algorithm for finding optimum partitions of simple monotone rectilinear polygons into star-shaped polygons. The algorithm may introduce Steiner points and its time complexity isO(n), wheren is the number of vertices in the polygon. We then use this algorithm to obtain anO(n logn) approximation algorithm for partitioning simple rectilinear polygons into star-shaped polygons with the size of the partition being at most six times the optimum.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759071
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 89
    Electronic Resource
    Electronic Resource
    Computational geometry algorithms for the systolic screen (1991)
    Springer
    Algorithmica 6 (1991), S. 734-761 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Clustering ; Convex hull ; Digitized pictures ; Hulls ; Maxima ; Mesh-of-processors ; Parallel computing ; Separability ; Systolic array ; Visibility ; Voronoi diagram
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Adigitized plane Π of sizeM is a rectangular √M × √M array of integer lattice points called pixels. A √M × √M mesh-of-processors in which each processorP ij represents pixel (i,j) is a natural architecture to store and manipulate images in Π; such a parallel architecture is called asystolic screen. In this paper we consider a variety of computational-geometry problems on images in a digitized plane, and present optimal algorithms for solving these problems on a systolic screen. In particular, we presentO(√M)-time algorithms for determining all contours of an image; constructing all rectilinear convex hulls of an image (peeling); solving the parallel and perspective visibility problem forn disjoint digitized images; and constructing the Voronoi diagram ofn planar objects represented by disjoint images, for a large class of object types (e.g., points, line segments, circles, ellipses, and polygons of constant size) and distance functions (e.g., allL p metrics). These algorithms implyO(√M)-time solutions to a number of other geometric problems: e.g., rectangular visibility, separability, detection of pseudo-star-shapedness, and optical clustering. One of the proposed techniques also leads to a new parallel algorithm for determining all longest common subsequences of two words.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759069
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 90
    Electronic Resource
    Electronic Resource
    Effect of the subdivision strategy on convergence and efficiency of some global optimization algorithms (1991)
    Springer
    Journal of global optimization 1 (1991), S. 23-36 
    Details
    ISSN: 1573-2916
    Keywords: Branch and bound ; global optimization ; subdivision strategy ; exhaustive and weakly exhaustive subdivision processes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We investigate subdivision strategies that can improve the convergence and efficiency of some branch and bound algorithms of global optimization. In particular, a general class of so called weakly exhaustive simplicial subdivision processes is introduced that subsumes all previously known radial exhaustive processes. This result provides the basis for constructing flexible subdivision strategies that can be adapted to take advantage of various problem conditions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00120663
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 91
    Electronic Resource
    Electronic Resource
    Mathematical programs with a two-dimensional reverse convex constraint (1991)
    Springer
    Journal of global optimization 1 (1991), S. 145-154 
    Details
    ISSN: 1573-2916
    Keywords: Reverse convex program ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We consider the problem min {f(x): x ∈ G, T(x) ∉ int D}, where f is a lower semicontinuous function, G a compact, nonempty set in ℝn, D a closed convex set in ℝ2 with nonempty interior and T a continuous mapping from ℝn to ℝ2. The constraint T(x) ∉ int D is a reverse convex constraint, so the feasible domain may be disconnected even when f, T are affine and G is a polytope. We show that this problem can be reduced to a quasiconcave minimization problem over a compact convex set in ℝ2 and hence can be solved effectively provided f, T are convex and G is convex or discrete. In particular we discuss a reverse convex constraint of the form 〈c, x〉 · 〈d, x〉≤1. We also compare the approach in this paper with the parametric approach.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00119988
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 92
    Electronic Resource
    Electronic Resource
    On solving a D.C. programming problem by a sequence of linear programs (1991)
    Springer
    Journal of global optimization 1 (1991), S. 183-203 
    Details
    ISSN: 1573-2916
    Keywords: Nonlinear programming ; global optimization ; d.c. programming ; branch and bound ; outer approximation ; prismatic partition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We are dealing with a numerical method for solving the problem of minimizing a difference of two convex functions (a d.c. function) over a closed convex set in ℝ n . This algorithm combines a new prismatic branch and bound technique with polyhedral outer approximation in such a way that only linear programming problems have to be solved.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00119991
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 93
    Electronic Resource
    Electronic Resource
    Algorithms for the single-source uncapacitated minimum concave-cost network flow problem (1991)
    Springer
    Journal of global optimization 1 (1991), S. 245-265 
    Details
    ISSN: 1573-2916
    Keywords: Concave-cost network flow ; uncapacitated ; single ; source ; global optimization ; local optimization ; complexity theory ; NP-hard
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We investigate algorithms, applications, and complexity issues for the single-source uncapacitated (SSU) version of the minimum concave-cost network flow problem (MCNFP). We present applications arising from production planning, and prove complexity results for both global and local search. We formally state the local search algorithm of Gallo and Sodini [5], and present alternative local search algorithms. Computational results are provided to compare the various local search algorithms proposed and the effects of initial solution techniques.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00119934
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 94
    Electronic Resource
    Electronic Resource
    Global search algorithms for minimum concave-cost network flow problems (1991)
    Springer
    Journal of global optimization 1 (1991), S. 309-330 
    Details
    ISSN: 1573-2916
    Keywords: Concave-cost network flow ; uncapacitated ; single-source ; global optimization ; random search algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We present algorithms for the single-source uncapacitated version of the minimum concave cost network flow problem. Each algorithm exploits the fact that an extreme feasible solution corresponds to a sub-tree of the original network. A global search heuristic based on random extreme feasible initial solutions and local search is developed. The algorithm is used to evaluate the complexity of the randomly generated test problems. An exact global search algorithm is developed, based on enumerative search of rooted subtrees. This exact technique is extended to bound the search based on cost properties and linear underestimation. The technique is accelerated by exploiting the network structure.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00130828
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 95
    Electronic Resource
    Electronic Resource
    A global optimization approach for solving the convex multiplicative programming problem (1991)
    Springer
    Journal of global optimization 1 (1991), S. 341-357 
    Details
    ISSN: 1573-2916
    Keywords: Multiplicative programming ; global optimization ; decomposition ; outer approximation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We consider a convex multiplicative programming problem of the form % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9qq-f0-yqaqVeLsFr0-vr% 0-vr0db8meaabaqaciGacaGaaeqabaWaaeaaeaaakeaacaGG7bGaam% OzamaaBaaaleaacaaIXaaabeaakiaacIcacaWG4bGaaiykaiabgwSi% xlaadAgadaWgaaWcbaGaaGOmaaqabaGccaGGOaGaamiEaiaacMcaca% GG6aGaamiEaiabgIGiolaadIfacaGG9baaaa!4A08!\[\{ f_1 (x) \cdot f_2 (x):x \in X\} \] where X is a compact convex set of ℝ n and f 1, f 2 are convex functions which have nonnegative values over X. Using two additional variables we transform this problem into a problem with a special structure in which the objective function depends only on two of the (n+2) variables. Following a decomposition concept in global optimization we then reduce this problem to a master problem of minimizing a quasi-concave function over a convex set in ℝ2 2. This master problem can be solved by an outer approximation method which requires performing a sequence of simplex tableau pivoting operations. The proposed algorithm is finite when the functions f i, (i=1, 2) are affine-linear and X is a polytope and it is convergent for the general convex case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00130830
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 96
    Electronic Resource
    Electronic Resource
    A trajectory algorithm based on the gradient method I. The search on the quasioptimal trajectories (1991)
    Springer
    Journal of global optimization 1 (1991), S. 375-388 
    Details
    ISSN: 1573-2916
    Keywords: Projected subgradient method ; global optimization ; trajectory algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The global optimization problem is considered under the assumption that the objective function is convex with respect to some variables. A finite subgradient algorithm for the search of an ε-optimal solution is proposed. Results of numerical experiments are presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00130832
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 97
    Electronic Resource
    Electronic Resource
    Weak convergence of Markov chain sampling methods and annealing algorithms to diffusions (1991)
    Springer
    Journal of optimization theory and applications 68 (1991), S. 483-498 
    Details
    ISSN: 1573-2878
    Keywords: Annealing algorithms ; sampling methods ; diffusion approximation ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Simulated annealing algorithms have traditionally been developed and analyzed along two distinct lines: Metropolis-type Markov chain algorithms and Langevin-type Markov diffusion algorithms. Here, we analyze the dynamics of continuous state Markov chains which arise from a particular implementation of the Metropolis and heat-bath Markov chain sampling methods. It is shown that certain continuous-time interpolations of the Metropolis and heat-bath chains converge weakly to Langevin diffusions running at different time scales. This exposes a close and potentially useful relationship between the Markov chain and diffusion versions of simulated annealing.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00940066
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 98
    Electronic Resource
    Electronic Resource
    Minimum concave-cost network flow problems: Applications, complexity, and algorithms (1990)
    Springer
    Annals of operations research 25 (1990), S. 75-99 
    Details
    ISSN: 1572-9338
    Keywords: Concave-cost network flow ; global optimization ; complexity theory ; NP-hard transportation problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We discuss a wide range of results for minimum concave-cost network flow problems, including related applications, complexity issues, and solution techniques. Applications from production and inventory planning, and transportation and communication network design are discussed. New complexity results are proved which show that this problem is NP-hard for cases with cost functions other than fixed charge. An overview of solution techniques for this problem is presented, with some new results given regarding the implementation of a particular branch-and-bound approach.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02283688
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 99
    Electronic Resource
    Electronic Resource
    An explicit characterization of the convex envelope of a bivariate bilinear function over special polytopes (1990)
    Springer
    Annals of operations research 25 (1990), S. 197-209 
    Details
    ISSN: 1572-9338
    Keywords: Convex envelopes ; bilinear functions ; bilinear programming problems ; global optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract In this paper, we constructively derive an explicit characterization of the convex envelope of a bilinear function over a special type of polytope in ℝ2. Our motivation stems from the use of such functions for deriving strengthened lower bounds within the context of a branch-and-bound algorithm for solving bilinear programming problems. For the case of polytopes with no edges having finite positive slopes, that is polytopes with “downward” sloping edges (which we call D-polytopes), we obtain a direct, explicit characterization of the convex envelope. This case subsumes the analysis of Al-Khayyal and Falk (1983) for constructing the convex envelope of a bilinear function over a rectangle in ℝ2. For non-D-polytopes, the analysis is more complex. We propose three strategies for this case based on (i) encasing the region in a D-polytope, (ii) employing a discretization technique, and (iii) providing an explicit characterization over a triangle along with a triangular decomposition approach. The analysis is illustrated using numerical examples.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02283695
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 100
    Electronic Resource
    Electronic Resource
    Interval Newton/generalized bisection when there are singularities near roots (1990)
    Springer
    Annals of operations research 25 (1990), S. 181-196 
    Details
    ISSN: 1572-9338
    Keywords: Nonlinear algebraic systems ; Newton's method ; interval arithmetic ; Gauss-Seidel method ; global optimization ; singularities
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Interval Newton methods in conjunction with generalized bisection are important elemetns of algorithms which find theglobal optimum within a specified box X ⊂ ℝn of an objective function ϕ whose critical points are solutions to the system of nonlinear equationsF(X)=0with mathematical certainty, even in finite presision arithmetic. The overall efficiency of such a scheme depends on the power of the interval Newton method to reduce the widths of the coordinate intervals of the box. Thus, though the generalized bisection method will still converge in a box which contains a critical point at which the Jacobian matrix is singular, the process is much more costly in that case. Here, we propose modifications which make the generalized bisection method isolate singular solutions more efficiently. These modifications are based on an observation about the verification property of interval Newton methods and on techniques for detecting the singularity and removing the region containing it. The modifications assume no special structure forF. Additionally, one of the observations should also make the algorithm more efficient when finding nonsingular solutions. We present results of computational experiments.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02283694
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...