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
    Construction of ɛ-nets (1990)
    Springer
    Discrete & computational geometry 5 (1990), S. 427-448 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetS be a set ofn points in the plane and letɛ be a real number, 0〈ɛ〈1. We give a deterministic algorithm, which in timeO(nɛ −2 log(1/ɛ)+ɛ −8) (resp.O(nɛ −2 log(1/ɛ)+ɛ −10) constructs anɛ-netN⊂S of sizeO((1/ɛ) (log(1/ɛ))2) for intersections ofS with double wedges (resp. triangles); this means that any double wedge (resp. triangle) containing more thatɛn points ofS contains a point ofN. This givesO(n logn) deterministic preprocessing for the simplex range-counting algorithm of Haussler and Welzl [HW] (in the plane). We also prove that given a setL ofn lines in the plane, we can cut the plane intoO(ɛ −2) triangles in such a way that no triangle is intersected by more thanɛn lines ofL. We give a deterministic algorithm for this with running timeO(nɛ −2 log(1/ɛ)). This has numerous applications in various computational geometry problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187804
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Efficient partition trees (1992)
    Springer
    Discrete & computational geometry 8 (1992), S. 315-334 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We prove a theorem on partitioning point sets inE d (d fixed) and give an efficient construction of partition trees based on it. This yields a simplex range searching structure with linear space,O(n logn) deterministic preprocessing time, andO(n 1−1/d (logn) O(1)) query time. WithO(nlogn) preprocessing time, where δ is an arbitrary positive constant, a more complicated data structure yields query timeO(n 1−1/d (log logn) O(1)). This attains the lower bounds due to Chazelle [C1] up to polylogarithmic factors, improving and simplifying previous results of Chazelleet al. [CSW]. The partition result implies that, forr d≤n 1−δ, a (1/r)-approximation of sizeO(r d) with respect to simplices for ann-point set inE d can be computed inO(n logr) deterministic time. A (1/r)-cutting of sizeO(r d) for a collection ofn hyperplanes inE d can be computed inO(n logr) deterministic time, provided thatr≤n 1/(2d−1).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02293051
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Discrepancy and approximations for bounded VC-dimension (1993)
    Springer
    Combinatorica 13 (1993), S. 455-466 
    Details
    ISSN: 1439-6912
    Keywords: 05 C 65 ; 52 C 99 ; 05 A 05 ; 52 C 10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Let (X, ℛ) be a set system on ann-point setX. For a two-coloring onX, itsdiscrepancy is defined as the maximum number by which the occurrences of the two colors differ in any set in ℛ. We show that if for anym-point subset $$Y \subseteq X$$ the number of distinct subsets induced by ℛ onY is bounded byO(m d) for a fixed integerd, then there is a coloring with discrepancy bounded byO(n 1/2−1/2d(logn)1+1/2d ). Also if any subcollection ofm sets of ℛ partitions the points into at mostO(m d) classes, then there is a coloring with discrepancy at mostO(n 1/2−1/2dlogn). These bounds imply improved upper bounds on the size of ε-approximations for (X, ℛ). All the bounds are tight up to polylogarithmic factors in the worst case. Our results allow to generalize several results of Beck bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01303517
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    On the Signed Domination in Graphs (2000)
    Springer
    Combinatorica 20 (2000), S. 103-108 
    Details
    ISSN: 1439-6912
    Keywords: AMS Subject Classification (1991) Classes:  05C78, 05D15
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: G on n vertices with minimum degree r, there exists a two-coloring of the vertices of G with colors +1 and -1, such that the closed neighborhood of each vertex contains more +1's than -1's, and altogether the number of 1's does not exceed the number of -1's by more than . As a construction by Füredi and Mubayi shows, this is asymptotically tight. The proof uses the partial coloring method from combinatorial discrepancy theory.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004930070034
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    List of publications on human biometeorology in Czechoslovakia (period 1920–1960) (1962)
    Springer
    International journal of biometeorology 5 (1962), S. 82-93 
    Details
    ISSN: 1432-1254
    Source: Springer Online Journal Archives 1860-2000
    Topics: Geography , Physics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02186056
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Improved upper bounds for approximation by zonotopes (1996)
    Springer
    Acta mathematica 177 (1996), S. 55-73 
    Details
    ISSN: 1871-2509
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02392598
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Book
    Book
    Lectures on discrete geometry; 212 (2002)
    New York u. a. :Springer,
    Details
    Title: Lectures on discrete geometry; 212
    Author: Matousek, Jiri
    Publisher: New York u. a. :Springer,
    Year of publication: 2002
    Pages: 481 S.
    Series Statement: Graduate texts in mathematics 212
    ISBN: 0-387-95374-4
    Type of Medium: Book
    Language: German
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
  • 8
    Book
    Book
    Invitation to discrete mathematics / (2009)
    Oxford [u.a.] :Oxford Univ. Press,
    Details
    Title: Invitation to discrete mathematics /
    Author: Matoušek, Jiří
    Contributer: Nešetřil, Jaroslav
    Edition: 2. ed.
    Publisher: Oxford [u.a.] :Oxford Univ. Press,
    Year of publication: 2009
    Pages: XVII, 443 S. : , Ill., graph. Darst. ; , 24 cm
    ISBN: 0-19-857043-0 , 978-0-19-857043-1 , 0-19-857042-2 , 978-0-19-857042-4
    Type of Medium: Book
    Language: English
    URL: http://www.zentralblatt-math.org/zmath/en/search/?an=1152.05002
    URL: http://www.gbv.de/dms/bowker/toc/9780198570431.pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
  • 9
    Book
    Book
    Approximation algorithms and semidefinite programming / (2012)
    Berlin [u.a.] :Springer,
    Details
    Title: Approximation algorithms and semidefinite programming /
    Contributer: Gärtner, Bernd , Matoušek, Jiří
    Publisher: Berlin [u.a.] :Springer,
    Year of publication: 2012
    Pages: XI, 251 S. : , Ill., graph. Darst.
    ISBN: 978-3-642-22014-2 , 978-3-642-22015-9
    Type of Medium: Book
    Language: English
    URL: https://www.zbmath.org/?q=an:1257.90001
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...