Library

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
  • 1
    Electronic Resource
    Electronic Resource
    Finding Optimal Shadows of Polytopes (2000)
    Springer
    Discrete & computational geometry 24 (2000), S. 219-240 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. This paper deals with the problem of projecting polytopes in finite-dimensional Euclidean spaces on subspaces of given dimension so as to maximize or minimize the volume of the projection. As to the computational complexity of the underlying decision problems we show that maximizing the volume of the orthogonal projection on hyperplanes is already NP-hard for simplices. For minimization, the problem is easy for simplices but NP-hard for bipyramids over parallelotopes. Similar results are given for projections on lower-dimensional subspaces. Several other related NP-hardness results are also proved including one for inradius computation of zonotopes and another for a location problem. On the positive side, we present various polynomial-time approximation algorithms. In particular, we give a randomized algorithm for maximizing orthogonal projections of CH-polytopes in R n on hyperplanes with an error bound of essentially $O(\sqrt{n/\log n})$ .
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004540010029
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    On Helly's Theorem: Algorithms and Extensions (1997)
    Springer
    Discrete & computational geometry 17 (1997), S. 393-410 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. This paper studies algorithmic Helly-type problems in the framework of the algorithmic theory of convex bodies developed by Grötschel, Lovász, and Schrijver. Various oracle-polynomial-time algorithms are presented that are complemented by ${\Bbb N \Bbb P}$ -hardness results for polytopes. In addition, some new Helly-type theorems are derived.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009300
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Finite sphere packing and sphere covering (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 19-40 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A basic problem of finite packing and covering is to determine, for a given number ofk unit balls in Euclideand-spaceE d , (1) the minimal volume of all convex bodies into which thek balls can be packed and (2) the maximal volume of all convex bodies which can be covered by thek balls. In the sausage conjectures by L. Fejes Tóth and J. M. Wills it is conjectured that, for alld≥5, linear arrangements of thek balls are best possible. In the paper several partial results are given to support both conjectures. Furthermore, some relations between finite and infinite (space) packing and covering are investigated.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187713
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    The interaction of systems integration, assembly, disassembly and maintenance in developing the intor-net mechanical configuration
    Amsterdam : Elsevier
    Fusion Engineering and Design 1 (1984), S. 115-125 
    Details
    ISSN: 0920-3796
    Source: Elsevier Journal Backfiles on ScienceDirect 1907 - 2002
    Topics: Energy, Environment Protection, Nuclear Power Engineering , Physics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1016/S0920-3796(84)80012-5
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Computational complexity of norm-maximization (1990)
    Springer
    Combinatorica 10 (1990), S. 203-225 
    Details
    ISSN: 1439-6912
    Keywords: 90 C 30 ; 68 Q 15 ; 52 A 25 ; 90 C 20 ; 90 C 09 ; 52 A 20
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract This paper discusses the problem of maximizing a quasiconvex functionφ over a convex polytopeP inn-space that is presented as the intersection of a finite number of halfspaces. The problem is known to beNP-hard (for variablen) whenφ is thep th power of the classicalp-norm. The present reexamination of the problem establishesNP-hardness for a wider class of functions, and for thep-norm it proves theNP-hardness of maximization overn-dimensionalparallelotopes that are centered at the origin or have a vertex there. This in turn implies theNP-hardness of {−1, 1}-maximization and {0, 1}-maximization of a positive definite quadratic form. On the “good” side, there is an efficient algorithm for maximizing the Euclidean norm over an arbitraryrectangular parallelotope.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02123011
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    On finite multiple packings (1990)
    Springer
    Archiv der Mathematik 55 (1990), S. 407-411 
    Details
    ISSN: 1420-8938
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01198482
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Polyedrische 2-Mannigfaltigkeiten mit wenigen nicht-konvexen Ecken (1984)
    Springer
    Monatshefte für Mathematik 97 (1984), S. 1-21 
    Details
    ISSN: 1436-5081
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract LetP denote a polyhedral 2-manifold in ℝ3, i.e. a 2-dimensional cell-complex in ℝ3 whose underlying point-set is a closed connected 2-manifold. A vertexv ofP is called convex if at least one of the two components into whichP divides a sufficiently small ball centered atv is convex. It is shown that every polyhedral 2-manifold in ℝ3 of genusg〉−1 contains at least five non-convex vertices and that for every positive integerg this bound is attained, i.e. there exists a polyhedral 2-manifold in ℝ3 of genusg with precisely five non-convex vertices.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01380888
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    On two finite covering problems of Bambah, Rogers, Woods and Zassenhaus (1985)
    Springer
    Monatshefte für Mathematik 99 (1985), S. 279-296 
    Details
    ISSN: 1436-5081
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Bambah, Rogers, Woods, and Zassenhaus considered the general problem of covering planar convex bodiesC byk translates of a centrally-symmetric convex bodyK ofE 2 with the ramification that these translates cover the convex hullC k of their centres. They proved interesting inequalities for the volume ofC andC k . In the present paper some analogous results in euclideand-spaceE d are given. It turns out that on one hand extremal configurations ford≥5 are of quite different type than in the planar case. On the other hand inequalities similar to the planar ones seem to exist in general. Inequalities in both directions for the volume and other quermass-integrals are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01312547
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Über L. Fejes Tóths Wurstvermutung in kleinen Dimensionen (1984)
    Springer
    Acta mathematica hungarica 43 (1984), S. 299-307 
    Details
    ISSN: 1588-2632
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01958027
    Library Location Call Number Volume/Issue/Year 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...