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
  • 1
    Electronic Resource
    Electronic Resource
    An upper bound for families of linearly related plane convex sets (1988)
    Springer
    Archiv der Mathematik 50 (1988), S. 56-58 
    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/BF01313495
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Weaving patterns of lines and line segments in space (1993)
    Springer
    Algorithmica 9 (1993), S. 561-571 
    Details
    ISSN: 1432-0541
    Keywords: Line weavings ; Lines in space
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Aweaving W is a simple arrangement of lines (or line segments) in the plane together with a binary relation specifying which line is “above” the other. A system of lines (or line segments) in 3-space is called arealization ofW, if its projection into the plane isW and the “above-below” relations between the lines respect the specifications. Two weavings are equivalent if the underlying arrangements of lines are combinatorially equivalent and the “above-below” relations are the same. An equivalence class of weavings is said to be aweaving pattern. A weaving pattern isrealizable if at least one element of the equivalence class has a three-dimensional realization. A weaving (pattern)W is calledperfect if, along each line (line segment) ofW, the lines intersecting it are alternately “above” and “below.” We prove that (i) a perfect weaving pattern ofn lines is realizable if and only ifn ≤ 3, (ii) a perfect m byn weaving pattern of line segments (in a grid-like fashion) is realizable if and only if min(m, n) ≤ 3, (iii) ifn is sufficiently large, then almost all weaving patterns ofn lines are nonrealizable.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190155
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Covering the plane with convex polygons (1986)
    Springer
    Discrete & computational geometry 1 (1986), S. 73-81 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract It is proved that for any centrally symmetric convex polygonal domainP and for any natural numberr, there exists a constantk=k(P, r) such that anyk-fold covering of the plane with translates ofP can be split intor simple coverings.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187684
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles (1986)
    Springer
    Discrete & computational geometry 1 (1986), S. 59-71 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Let γ1,..., γ m bem simple Jordan curves in the plane, and letK 1,...,K m be their respective interior regions. It is shown that if each pair of curves γ i , γ j ,i ≠j, intersect one another in at most two points, then the boundary ofK=∩ i =1m K i contains at most max(2,6m − 12) intersection points of the curvesγ 1, and this bound cannot be improved. As a corollary, we obtain a similar upper bound for the number of points of local nonconvexity in the union ofm Minkowski sums of planar convex sets. Following a basic approach suggested by Lozano Perez and Wesley, this can be applied to planning a collision-free translational motion of a convex polygonB amidst several (convex) polygonal obstaclesA 1,...,A m . Assuming that the number of corners ofB is fixed, the algorithm presented here runs in timeO (n log2 n), wheren is the total number of corners of theA i 's.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187683
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 291-309 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Letf 1, ...,f m be (partially defined) piecewise linear functions ofd variables whose graphs consist ofn d-simplices altogether. We show that the maximal number ofd-faces comprising the upper envelope (i.e., the pointwise maximum) of these functions isO(n d α(n)), whereα(n) denotes the inverse of the Ackermann function, and that this bound is tight in the worst case. If, instead of the upper envelope, we consider any single connected componentC enclosed byn d-simplices (or, more generally, (d − 1)-dimensional compact convex sets) in ℝ d+1 , then we show that the overall combinatorial complexity of the boundary ofC is at mostO(n d+1−ɛ(d+1) ) for some fixed constantɛ(d+1)〉0.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187732
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    On arrangements of Jordan arcs with three intersections per pair (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 523-539 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union ofn regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan acrs in the upper halfplane starting and ending on thex-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only Θ(nα(n)), whereα(n) is the extremely slowly growing functional inverse of Ackermann's function.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187745
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    An upper bound on the number of planarK-sets (1992)
    Springer
    Discrete & computational geometry 7 (1992), S. 109-123 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a setS ofn points, a subsetX of sizek is called ak-set if there is a hyperplane Π that separatesX fromS−X. We prove thatO(n√k/log*k) is an upper bound for the number ofk-sets in the plane, thus improving the previous bound of Erdös, Lovász, Simmons, and Strauss by a factor of log*k.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187829
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Almost tight bounds forɛ-Nets (1992)
    Springer
    Discrete & computational geometry 7 (1992), S. 163-173 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given any natural numberd, 0〈ɛ〈1, letf d (ɛ) denote the smallest integerf such that every range space of Vapnik-Chervonenkis dimensiond has anɛ-net of size at mostf. We solve a problem of Haussler and Welzl by showing that ifd≥2, then $$d - 2 + \frac{2}{{d + 2}} \leqslant \mathop {\lim }\limits_{\varepsilon \to 0} \frac{{f_d (\varepsilon )}}{{(1/\varepsilon )\log (1/\varepsilon )}} \leqslant d.$$ Further, we prove thatf 1(ɛ)=max(2, ⌌ 1/ɛ ⌍−1), and similar bounds are established for some special classes of range spaces of Vapnik-Chervonenkis dimension three.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187833
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    On the maximal number of certain subgraphs inK r -free graphs (1991)
    Springer
    Graphs and combinatorics 7 (1991), S. 31-37 
    Details
    ISSN: 1435-5914
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given two graphsH andG, letH(G) denote the number of subgraphs ofG isomorphic toH. We prove that ifH is a bipartite graph with a one-factor, then for every triangle-free graphG withn verticesH(G) ≤ H(T 2(n)), whereT 2(n) denotes the complete bipartite graph ofn vertices whose colour classes are as equal as possible. We also prove that ifK is a completet-partite graph ofm vertices,r 〉 t, n ≥ max(m, r − 1), then there exists a complete (r − 1)-partite graphG* withn vertices such thatK(G) ≤ K(G*) holds for everyK r -free graphG withn vertices. In particular, in the class of allK r -free graphs withn vertices the complete balanced (r − 1)-partite graphT r−1(n) has the largest number of subgraphs isomorphic toK t (t 〈 r),C 4,K 2,3. These generalize some theorems of Turán, Erdös and Sauer.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01789461
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Erdős–Szekeres-Type Theorems for Segments and Noncrossing Convex Sets (2000)
    Springer
    Geometriae dedicata 81 (2000), S. 1-12 
    Details
    ISSN: 1572-9168
    Keywords: Ramsey's theorem ; Erdős-Szekeres theorem ; convexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A family $$\mathcal{F}$$ of convex sets is said to be in convex position, if none of its members is contained in the convex hull of the others. It is proved that there is a function N(n) with the following property. If $$\mathcal{F}$$ is a family of at least N(n) plane convex sets with nonempty interiors, such that any two members of $$\mathcal{F}$$ have at most two boundary points in common and any three are in convex position, then $$\mathcal{F}$$ has n members in convex position. This result generalizes a theorem of T. Bisztriczky and G. Fejes Tóth. The statement does not remain true, if two members of $$\mathcal{F}$$ may share four boundary points. This follows from the fact that there exist infinitely many straight-line segments such that any three are in convex position, but no four are. However, there is a function M(n) such that every family of at least M(n) segments, any four of which are in convex position, has n members in convex position.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1005210202899
    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...