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
    Approximation Algorithms for Minimum-Width Annuli and Shells (2000)
    Springer
    Discrete & computational geometry 24 (2000), S. 687-705 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Let S be a set of n points in \re d . The ``roundness'' of S can be measured by computing the width ω * =ω * (S) of the thinnest spherical shell (or annulus in \re 2 ) that contains S . This paper contains two main results related to computing an approximation of ω * : (i) For d=2 , we can compute in O(n log n) time an annulus containing S whose width is at most 2ω * (S) . We extend this algorithm, so that, for any given parameter ε 〉0 , an annulus containing S whose width is at most (1+ε )ω * is computed in time O(n log n + n/ε 2 ) . (ii) For d \geq 3 , given a parameter ε 〉 0 , we can compute a shell containing S of width at most (1+ε)ω * either in time O ( n / ε d ) log ( \Delata / ω * ε ) or in time O ( n / ε d-2 ) log  n + 1 / εlog  \Delata / ω * ε , where Δ is the diameter of S .
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004540010062
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Motion Planning for a Convex Polygon in a Polygonal Environment (1999)
    Springer
    Discrete & computational geometry 22 (1999), S. 201-221 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We study the motion-planning problem for a convex m -gon P in a planar polygonal environment Q bounded by n edges. We give the first algorithm that constructs the entire free configuration space (the three-dimensional space of all free placements of P in Q ) in time that is near-quadratic in mn , which is nearly optimal in the worst case. The algorithm is also conceptually simple. Previous solutions were incomplete, more expensive, or produced only part of the free configuration space. Combining our solution with parametric searching, we obtain an algorithm that finds the largest placement of P in Q in time that is also near-quadratic in mn . In addition, we describe an algorithm that preprocesses the computed free configuration space so that reachability queries can be answered in polylogarithmic time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009455
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    On Levels in Arrangements of Lines, Segments, Planes, and Triangles% (1998)
    Springer
    Discrete & computational geometry 19 (1998), S. 315-331 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We consider the problem of bounding the complexity of the k th level in an arrangement of n curves or surfaces, a problem dual to, and an extension of, the well-known k-set problem. Among other results, we prove a new bound, O(nk 5/3 ) , on the complexity of the k th level in an arrangement of n planes in R 3 , or on the number of k -sets in a set of n points in three dimensions, and we show that the complexity of the k th level in an arrangement of n line segments in the plane is $O(n\sqrt{k}\alpha(n/k))$ , and that the complexity of the k th level in an arrangement of n triangles in 3-space is O(n 2 k 5/6 α(n/k)) . 〈lsiheader〉 〈onlinepub〉26 June, 1998 〈editor〉Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; 〈pdfname〉19n3p315.pdf 〈pdfexist〉yes 〈htmlexist〉no 〈htmlfexist〉no 〈texexist〉yes 〈sectionname〉 〈/lsiheader〉
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009348
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Efficient Algorithms for Approximating Polygonal Chains (2000)
    Springer
    Discrete & computational geometry 23 (2000), S. 273-291 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We consider the problem of approximating a polygonal chain C by another polygonal chain C' whose vertices are constrained to be a subset of the set of vertices of C . The goal is to minimize the number of vertices needed in the approximation C' . Based on a framework introduced by Imai and Iri [25], we define an error criterion for measuring the quality of an approximation. We consider two problems. (1) Given a polygonal chain C and a parameter ɛ \geq 0 , compute an approximation of C , among all approximations whose error is at most ɛ , that has the smallest number of vertices. We present an O(n 4/3 + δ ) -time algorithm to solve this problem, for any δ 〉 0; the constant of proportionality in the running time depends on δ . (2) Given a polygonal chain C and an integer k , compute an approximation of C with at most k vertices whose error is the smallest among all approximations with at most k vertices. We present a simple randomized algorithm, with expected running time O(n 4/3 + δ ) , to solve this problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009500
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Lower Bounds for Kinetic Planar Subdivisions (2000)
    Springer
    Discrete & computational geometry 24 (2000), S. 721-733 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We revisit the notion of kinetic efficiency for noncanonically defined discrete attributes of moving data, like binary space partitions and triangulations. Under reasonable computational models, we obtain lower bounds on the minimum amount of work required to maintain any binary space partition of moving segments in the plane or any Steiner triangulation of moving points in the plane. Such lower bounds—the first to be obtained in the kinetic context—are necessary to evaluate the efficiency of kinetic data structures when the attribute to be maintained is not canonically defined.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004540010060
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Largest Placement of One Convex Polygon Inside Another (1998)
    Springer
    Discrete & computational geometry 19 (1998), S. 95-104 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We show that the largest similar copy of a convex polygon P with m edges inside a convex polygon Q with n edges can be computed in O(mn 2 log n) time. We also show that the combinatorial complexity of the space of all similar copies of P inside Q is O(mn 2 ) , and that it can also be computed in O(mn 2 log n) time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009337
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions (1999)
    Springer
    Discrete & computational geometry 21 (1999), S. 373-388 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We establish a near-cubic upper bound on the complexity of the space of line transversals of a collection of n balls in three dimensions, and show that the bound is almost tight, in the worst case. We apply this bound to obtain a near-cubic algorithm for computing a smallest infinite cylinder enclosing a given set of points or balls in 3-space. We also present an approximation algorithm for computing a smallest enclosing cylinder.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009427
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    The Discrete 2-Center Problem (1998)
    Springer
    Discrete & computational geometry 20 (1998), S. 287-305 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of smallest possible radius, centered at two points of P , whose union covers P . Our algorithm runs in time O(n 4/3 log 5 n) .
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009387
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Dynamic half-space range reporting and its applications (1995)
    Springer
    Algorithmica 13 (1995), S. 325-345 
    Details
    ISSN: 1432-0541
    Keywords: Arrangements ; Cuttings ; Range-searching ; Dynamization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the half-space range-reporting problem: Given a setS ofn points in ℝd, preprocess it into a data structure, so that, given a query half-space γ, allk points ofS ∩ γ can be reported efficiently. We extend previously known static solutions to dynamic ones, supporting insertions and deletions of points ofS. For a given parameterm,n ≤m ≤n ⌊d/2⌋ and an arbitrarily small positive constant ɛ, we achieveO(m 1+ɛ) space and preprocessing time, O((n/m ⌊d/2⌋ logn+k) query time, and O(m1+ɛn) amortized update time (d ≳ 3). We present, among others, the following applications: an O(n1+ɛ)-time algorithm for computing convex layers in ℝ3, and an output sensitive algorithm for computing a level in an arrangements of planes in ℝ3, whose time complexity is O((b+n) nɛ, whereb is the size of the level.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01293483
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Connected component and simple polygon intersection searching (1996)
    Springer
    Algorithmica 15 (1996), S. 626-660 
    Details
    ISSN: 1432-0541
    Keywords: Arrangements ; Data structures ; Intersection searching ; Partition trees
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Efficient data structures are given for the following two query problems: (i) preprocess a setP of simple polygons with a total ofn edges, so that all polygons ofP intersected by a query segment can be reported efficiently, and (ii) preprocess a setS ofn segments, so that the connected components of the arrangement ofS intersected by a query segment can be reported quickly. In these problems we do not want to return the polygons or connected components explicitly (i.e., we do not wish to report the segments defining the polygon, or the segments lying in the connected components). Instead, we assume that the polygons (or connected components) are labeled and we just want to report their labels. We present data structures of sizeO(n 1+ε) that can answer a query in timeO(n 1+ε+k), wherek is the output size. If the edges ofP (or the segments inS) are orthogonal, the query time can be improved toO(logn+k) usingO(n logn) space. We also present data structures that can maintain the connected components as we insert new segments. For arbitrary segments the amortized update and query time areO(n 1/2+ε) andO(n 1/2+ε+k), respectively, and the space used by the data structure isO(n 1+ε. If we allowO(n 4/3+ε space, the amortized update and query time can be improved toO(n 1/3+ε andO(n 1/3+ε+k, respectively. For orthogonal segments the amortized update and query time areO(log2 n) andO(log2 n+klogn), and the space used by the data structure isO (n logn). Some other related results are also mentioned.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01940884
    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...