Jack Snoeyink

  1. On Finding Non-dominated Points using Compact Voronoi Diagrams.

    Authors: Binay Bhattacharya, Arijit Bishnu, Otfried Cheong, Sandip Das, Arindam Karmakar, Jack Snoeyink
    Subjects: Computational Geometry
    Abstract

    We discuss in this paper a method of finding skyline or non-dominated points
    in a set $P$ of $n_P$ points with respect to a set $S$ of $n_S$ sites. A point
    $p_i \in P$ is non-dominated if and only if for each $p_j \in P$, $j \not= i$,
    there exists at least one point $s \in S$ that is closer to $p_i$ than $p_j$.
    We reduce this problem of determining non-dominated points to the problem of
    finding sites that have non-empty cells in an additive Voronoi diagram with a
    convex distance function.

Syndicate content