Computing half-plane and strip discrepancy of planar point sets

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    4 Citaten (Scopus)

    Samenvatting

    We present efficient algorithms for two problems concerning the discrepancy of a set S of n points in the unit square in the plane. First, we describe an algorithm for maintaining the half-plane discrepancy of S under insertions and deletions of points. The algorithm runs in O(nlogn) worst-case time per update, and it requires only relatively simple data structures. Second, we give an algorithm that computes the strip discrepancy of S in O(n2a(n)logn) time, where a(n) is the extremely slowly growing functional inverse of Ackermann's function.
    Originele taal-2Engels
    Pagina's (van-tot)69-83
    Aantal pagina's15
    TijdschriftComputational Geometry
    Volume6
    Nummer van het tijdschrift2
    DOI's
    StatusGepubliceerd - 1996

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Computing half-plane and strip discrepancy of planar point sets'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit