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
    Approximating Minimum-Weight Triangulations in Three Dimensions (1999)
    Springer
    Discrete & computational geometry 21 (1999), S. 527-549 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Let S be a set of noncrossing triangular obstacles in R 3 with convex hull H . A triangulation T of H is compatible with S if every triangle of S is the union of a subset of the faces of T. The weight of T is the sum of the areas of the triangles of T. We give a polynomial-time algorithm that computes a triangulation compatible with S whose weight is at most a constant times the weight of any compatible triangulation. One motivation for studying minimum-weight triangulations is a connection with ray shooting. A particularly simple way to answer a ray-shooting query (``Report the first obstacle hit by a query ray'') is to walk through a triangulation along the ray, stopping at the first obstacle. Under a reasonably natural distribution of query rays, the average cost of a ray-shooting query is proportional to triangulation weight. A similar connection exists for line-stabbing queries (``Report all obstacles hit by a query line'').
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009436
    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 Multiple Robots (1999)
    Springer
    Discrete & computational geometry 22 (1999), S. 505-525 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We study the motion-planning problem for pairs and triples of robots operating in a shared workspace containing n obstacles. A standard way to solve such problems is to view the collection of robots as one composite robot, whose number of degrees of freedom is d , the sum of the numbers of degrees of freedom of the individual robots. We show that it is sufficient to consider a constant number of robot systems whose number of degrees of freedom is at most d-1 for pairs of robots, and d-2 for triples. (The result for a pair assumes that the sum of the number of degrees of freedom of the robots constituting the pair reduces by at least one if the robots are required to stay in contact; for triples a similar assumption is made. Moreover, for triples we need to assume that a solution with positive clearance exists.) We use this to obtain an O(n d ) time algorithm to solve the motion-planning problem for a pair of robots; this is one order of magnitude faster than what the standard method would give. For a triple of robots the running time becomes O(n d-1 ) , which is two orders of magnitude faster than the standard method. We also apply our method to the case of a collection of bounded-reach robots moving in a low-density environment. Here the running time of our algorithm becomes O(n log n) both for pairs and triples.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009476
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Visibility with Multiple Reflections (1998)
    Springer
    Discrete & computational geometry 20 (1998), S. 61-78 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We show that the region lit by a point light source inside a simple n -gon after at most k reflections off the boundary has combinatorial complexity O(n 2k ) , for any k≥ 1 . A lower bound of Ω ((n/k-Θ(1)) 2k ) is also established which matches the upper bound for any fixed k . A simple near-optimal algorithm for computing the illuminated region is presented, which runs in O(n 2k log n) time and O(n 2k ) space for k〉1 , and in O(n 2 log 2 n) time and O(n 2 ) space for k=1 .
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009378
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    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
  • 5
    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
  • 6
    Electronic Resource
    Electronic Resource
    Visibility with One Reflection (1998)
    Springer
    Discrete & computational geometry 19 (1998), S. 553-574 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We extend the concept of the polygon visible from a source point S in a simple polygon by considering visibility with two types of reflection, specular and diffuse. In specular reflection a light ray reflects from an edge of the polygon according to the rule: the angle of incidence equals the angle of reflection. In diffuse reflection a light ray reflects from an edge of the polygon in all inward directions. Several geometric and combinatorial properties of visibility polygons under these two types of reflection are described, when at most one reflection is permitted. We show that the visibility polygon Vs(S) under specular reflection may be nonsimple, while the visibility polygon Vd(S) under diffuse reflection is always simple. We present a Θ(n 2 ) worst-case bound on the combinatorial complexity of both Vs(S) and Vd(S) and describe simple O(n 2 log 2 n) time algorithms for constructing the sets.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009368
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    On the Number of Regular Vertices of the Union of Jordan Regions (2001)
    Springer
    Discrete & computational geometry 25 (2001), S. 203-220 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Let \C be a collection of n Jordan regions in the plane in general position, such that each pair of their boundaries intersect in at most s points, where s is a constant. If the boundaries of two sets in \C cross exactly twice, then their intersection points are called regular vertices of the arrangement \A(\C) . Let R(\C) denote the set of regular vertices on the boundary of the union of \C . We present several bounds on |R(\C)| , depending on the type of the sets of \C . (i) If each set of \C is convex, then |R(\C)|=O(n 1.5+\eps ) for any \eps〉0 . (ii) If no further assumptions are made on the sets of \C , then we show that there is a positive integer r that depends only on s such that |R(\C)|=O(n 2-1/r ) . (iii) If \C consists of two collections \C 1 and \C 2 where \C 1 is a collection of m convex pseudo-disks in the plane (closed Jordan regions with the property that the boundaries of any two of them intersect at most twice), and \C 2 is a collection of polygons with a total of n sides, then |R(\C)|=O(m 2/3 n 2/3 +m +n) , and this bound is tight in the worst case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s00454-001-0001-7
    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 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
  • 9
    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
  • 10
    Electronic Resource
    Electronic Resource
    On the Helly Number for Hyperplane Transversals to Unit Balls (2000)
    Springer
    Discrete & computational geometry 24 (2000), S. 171-176 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We prove two results about the Hadwiger problem of finding the Helly number for line transversals of disjoint unit disks in the plane, and about its higher-dimensional generalization to hyperplane transversals of unit balls in d -dimensional Euclidean space. These consist of (a) a proof of the fact that the Helly number remains 5 even for arbitrarily large sets of disjoint unit disks—thus correcting a 40-year-old error; and (b) a lower bound of d+3 on the Helly number for hyperplane transversals to suitably separated families of unit balls in R d .
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004540010024
    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...