Bibliothek

X
feed icon rss

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
Filter
  • Computational geometry  (2)
  • Modified pruning technique  (1)
  • 1
    Digitale Medien
    Digitale Medien
    A linear-time algorithm for linearL 1 approximation of points (1989)
    Springer
    Algorithmica 4 (1989), S. 77-96 
    Details
    ISSN: 1432-0541
    Schlagwort(e): Computational geometry ; Modified pruning technique ; LinearL 1 approximation
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01553880
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 2
    Digitale Medien
    Digitale Medien
    Visibility of disjoint polygons (1986)
    Springer
    Algorithmica 1 (1986), S. 49-63 
    Details
    ISSN: 1432-0541
    Schlagwort(e): Computational geometry ; Computer graphics ; Robotics ; Visibility ; Hidden-line Elimination ; Visibility graph ; Shortest path
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n 2) time and space, a data structure from which inO(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed inO(n 2) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed inO(n 2) time, improving earlierO(n 2 logn) results.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01840436
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...