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
  • Articles  (75,300)
  • 1990-1994  (75,300)
  • Mathematics  (75,300)
Collection
Source
Keywords
Publisher
Years
Year
Journal
Topic
  • 1
    Electronic Resource
    Electronic Resource
    Classification of arrangements by the number of their cells (1993)
    Springer
    Discrete & computational geometry 9 (1993), S. 39-46 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The possible pairs (n, f) of integers for which there are arrangements withn lines andf cells are determined. The pair (n, f) corresponds to an arrangement if and only if there is an integerk with 0≤k≤n−2 such that $$(n - k)(k + 1) + \left( {_2^k } \right) - \min \left\{ {n - k,\left( {_2^k } \right)} \right\} \leqslant f \leqslant (n - k)(k + 1) + \left( {_2^k } \right).$$
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02189305
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Minimum dissection of a rectilinear polygon with arbitrary holes into rectangles (1993)
    Springer
    Discrete & computational geometry 9 (1993), S. 57-79 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, the problem of dissecting a plane rectilinear polygon with arbitrary (possibly, degenerate) holes into a minimum number of rectangles is shown to be solvable inO(n 3/2 logn) time. This fact disproves a famous assertion about the NP-hardness of the minimum rectangular dissection problem for rectilinear polygons with point holes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02189307
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Forthcoming papers (1993)
    Springer
    Discrete & computational geometry 9 (1993), S. 107-107 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02189310
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    The lower and upper bound problems for cubical polytopes (1993)
    Springer
    Discrete & computational geometry 9 (1993), S. 159-163 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We construct a family of cubical polytypes which shows that the upper bound on the number of facets of a cubical polytope (given a fixed number of vertices) is higher than previously suspected. We also formulate a lower bound conjecture for cubical polytopes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02189315
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Cutting hyperplanes for divide-and-conquer (1993)
    Springer
    Discrete & computational geometry 9 (1993), S. 145-158 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Givenn hyperplanes inE d, a (1/r)-cutting is a collection of simplices with disjoint interiors, which together coverE d and such that the interior of each simplex intersects at mostn/r hyperplanes. We present a deterministic algorithm for computing a (1/r)-cutting ofO(r d) size inO(nr d−1) time. If we require the incidences between the hyperplanes and the simplices of the cutting to be provided, then the algorithm is optimal. Our method is based on a hierarchical construction of cuttings, which also provides a simple optimal data structure for locating a point in an arrangement of hyperplanes. We mention several other applications of our result, e.g., counting segment intersections, Hopcroft's line/point incidence problem, linear programming in fixed dimension.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02189314
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Successive-minima-type inequalities (1993)
    Springer
    Discrete & computational geometry 9 (1993), S. 165-175 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show analogues of Minkowski's theorem on successive minima, where the volume is replaced by the lattice point enumerator. We further give analogous results to some recent theorems by Kannan and Lovász on covering minima.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02189316
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    An equipartition of planar sets (1993)
    Springer
    Discrete & computational geometry 9 (1993), S. 257-266 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe the “cobweb” partition scheme and show that it can split any planar set into eight regions of equal area.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02189322
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    On convex body chasing (1993)
    Springer
    Discrete & computational geometry 9 (1993), S. 293-321 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A player moving in the plane is given a sequence of instructions of the following type: at stepi a planar convex setF i is specified, and the player has to move to a point inF i. The player is charged for the distance traveled. We provide a strategy for the player which is competitive, i.e., for any sequenceF i the cost to the player is within a constant (multiplicative) factor of the “off-line” cost (i.e., the least possible cost when allF i are known in advance). We conjecture that similar strategies can be developed for this game in any Euclidean space and perhaps even in all metric spaces. The analogous statement where convex sets are replaced by more general families of sets in a metric space includes many on-line/off-line problems such as thek-server problem; we make some remarks on these more general problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02189324
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    The upper envelope of voronoi surfaces and its applications (1993)
    Springer
    Discrete & computational geometry 9 (1993), S. 267-291 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a setS ofsources (points or segments) in ℜ211C;d, we consider the surface in ℜ211C; d+1 that is the graph of the functiond(x)=min pεS ρ(x, p) for some metricρ. This surface is closely related to the Voronoi diagram, Vor(S), ofS under the metricρ. The upper envelope of a set of theseVoronoi surfaces, each defined for a different set of sources, can be used to solve the problem of finding the minimum Hausdorff distance between two sets of points or line segments under translation. We derive bounds on the number of vertices on the upper envelope of a collection of Voronoi surfaces, and provide efficient algorithms to calculate these vertices. We then discuss applications of the methods to the problems of finding the minimum Hausdorff distance under translation, between sets of points and segments.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02189323
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    The steiner minimal network for convex configurations (1993)
    Springer
    Discrete & computational geometry 9 (1993), S. 323-333 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract SupposeX is a convex configuration with radius of maximum curvaturer and at most one of the edges joining neighboring points has length strictly greater thanr. We use the variational approach to show the Steiner treeS coincides with the minimal spanning tree and consists of all these edges with a longest edge removed. This generalizes Graham's problem for points on a circle, which we had solved. In addition we describe the minimal spanning tree for certain convex configurations.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02189325
    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...