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
    A linear-time algorithm for linearL 1 approximation of points (1989)
    Springer
    Algorithmica 4 (1989), S. 77-96 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Modified pruning technique ; LinearL 1 approximation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we present a linear-time algorithm for approximating a set ofn points by a linear function, or a line, that minimizes theL 1 norm. The algorithmic complexity of this problem appears not to have been investigated, although anO(n 3) naive algorithm can be easily obtained based on some simple characteristics of an optimumL 1 solution. Our linear-time algorithm is optimal within a constant factor and enables us to use linearL 1 approximation of many points in practice. The complexity ofL 1 linear approximation of a piecewise linear function is also touched upon.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01553880
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Computing the volume of the union of spheres (1988)
    Springer
    The visual computer 3 (1988), S. 323-328 
    Details
    ISSN: 1432-2315
    Keywords: Union of Spheres ; Volumes ; Laguerre Voronoid diagram ; Power diagram
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract OnO(n 2) exact algorithm is given for computing the volume of a set ofn spheres in space. The algorithm employs the Laguerre Voronoi (power) diagram and a method for computing the volume of the intersection of a simplex and a sphere exactly. We give a new proof of a special case of a conjecture, popularized by Klee, concerning the change in volume as the centres of the spheres become further apart.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901190
    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...