مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

video

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

sound

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Persian Version

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

View:

50
مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Download:

3
مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Cites:

Information Journal Paper

Title

Approximate $k$-nearest neighbor graph on moving points

Pages

  65-72

Keywords

$k$-Nearest Neighbor Graph 

Abstract

 In this paper, we introduce an approximation for the $k$-nearest neighbor graph ($k$-NNG) on a point set $P$ in $\mathbb{R}^d$. For any given $\varepsilon>0$, we construct a graph, that we call the \emph{approximate $k$-NNG}, where the edge with the $i$th smallest length incident to a point $p$ in this graph is within a factor of $(1+\varepsilon)$ of the length of the edge with the $i$th smallest length incident to $p$ in the $k$-NNG. For a set $P$ of $n$ Moving Points in $\mathbb{R}^d$, where the trajectory of each point $p\in P$ is given by $d$ polynomial functions of constant bounded degree, where each function gives one of the $d$ coordinates of $p$, we compute the number of combinatorial changes to the approximate $k$-NNG, and provide a kinetic data structure (KDS) for maintenance of the edges of the approximate $k$-NNG over time. Our KDS processes $O(kn^2\log^{d+1} n)$ events, each in time $O(\log^{d+1}n)$.

Multimedia

  • No record.

    • Cites

  • No record.

    • References

  • No record.

    • Cite

    Related Journal Papers

  • No record.

    • Related Seminar Papers

  • No record.

    • Related Plans

  • No record.

    • Recommended Workshops






    Move to top
    telegram sharing button
    whatsapp sharing button
    linkedin sharing button
    twitter sharing button
    email sharing button
    email sharing button
    email sharing button
    sharethis sharing button