مرکز اطلاعات علمی 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:

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

Download:

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

Cites:

Information Journal Paper

Title

On the maximum triangle problem

Pages

  1143-1148

Abstract

 Given a set $P$ of $n$ points in the plane, the Maximum triangle problem asks for finding a triangle with three vertices in $P$ that encloses the maximum number of points from $P$. While the problem is easily solvable in $O(n^3)$ time, it has been open whether a subcubic solution is possible. In this paper, we show that the problem can be solved in $o(n^3)$ time, using a reduction to min-plus matrix multiplication. We also provide some improved Approximation Algorithms for the problem, including a 4-approximation algorithm running in $O(n \log n \log h)$ time, and a 3-approximation algorithm with $O(nh \log n + nh^2)$ runtime, where $h$ is the size of the convex hull of $P$.

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