The mostlikely skyline problem for stochastic points Abstract   For a set O of n points in      R    d     , the skyline consists of the subset of all points of O where no point is dominated by any other point of O. Suppose that each point      o    i    xe2x88x88  O    has an associated probability of existence      p    i    xe2x88x88  (  0  ,  1     . The problem of computing the skyline with the maximum probability of occurrence is considered. It is shown that in      R    d     ,    d  xe2x89xa5  3   , the problem is NPhard and that the desired skyline cannot even be wellapproximated in polynomial time unless    P     NP    . In      R    2     , an optimal    O  (  n  log  xe2x81xa1  n  )   time and    O  (  n  )   space algorithm is given.

A Fully Polynomial Time Approximation Scheme for the Smallest Diameter of Imprecise Points Abstract   Given a set    D        d    1    ,  xe2x80xa6  ,    d    n        of imprecise points modeled as disks, the minimum diameter problem is to locate a set    P        p    1    ,  xe2x80xa6  ,    p    n        of fixed points, where      p    i    xe2x88x88    d    i     , such that the furthest distance between any pair of points in P is as small as possible. This introduces a tight lower bound on the size of the diameter of any instance P. In this paper, we present a fully polynomial time approximation scheme (FPTAS) for computing the minimum diameter of a set of disjoint disks that runs in    O  (    n    2      xcfxb5    xe2x88x92  1    )    time. Then we relax the disjointness assumption and provide a    O  (    n    2      xcfxb5    xe2x88x92  2    )    randomize algorithm. We also show that our results can be generalized in      R    d      when the dimension  d  is an arbitrary fixed constant.