Library

X
Language
Preferred search index
Number of Hits per Page
Default Sort Criterion
Default Sort Ordering
Size of Search History
Default Email Address
Default Export Format
Default Export Encoding
Facet list arrangement
Maximum number of values per filter
Auto Completion
Feed Format
Maximum Number of Items per Feed
Permalink If you want to be able to use settings permanently, you must save your settings and then set a Bookmark to the permalink
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
    Minkowski-Type Theorems and Least-Squares Clustering (1998)
    Springer
    Algorithmica 20 (1998), S. 61-76 
    Details
    ISSN: 1432-0541
    Keywords: Key words. Power diagrams, Least-squares clustering, Point partitioning.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Dissecting Euclidean d -space with the power diagram of n weighted point sites partitions a given m -point set into clusters, one cluster for each region of the diagram. In this manner, an assignment of points to sites is induced. We show the equivalence of such assignments to constrained Euclidean least-squares assignments. As a corollary, there always exists a power diagram whose regions partition a given d -dimensional m -point set into clusters of prescribed sizes, no matter where the sites are placed. Another consequence is that constrained least-squares assignments can be computed by finding suitable weights for the sites. In the plane, this takes roughly O(n 2 m) time and optimal space O(m) , which improves on previous methods. We further show that a constrained least-squares assignment can be computed by solving a specially structured linear program in n+1 dimensions. This leads to an algorithm for iteratively improving the weights, based on the gradient-descent method. Besides having the obvious optimization property, least-squares assignments are shown to be useful in solving a certain transportation problem, and in finding a least-squares fitting of two point sets where translation and scaling are allowed. Finally, we extend the concept of a constrained least-squares assignment to continuous distributions of points, thereby obtaining existence results for power diagrams with prescribed region volumes. These results are related to Minkowski's theorem for convex polytopes. The aforementioned iterative method for approximating the desired power diagram applies to continuous distributions as well.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009187
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    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
  • 3
    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
  • 4
    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
  • 5
    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
  • 6
    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
  • 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
    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
  • 9
    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
  • 10
    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
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...