2014/10/14 by Bahman Kalantari, Kalantari, Bahman
Computer Science · Mathematics · #68U05 #68W20 #90C05 #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Numerical Methods and Algorithms #cs.CG #msc:68U05 #msc:68W20 #msc:90C05
paper · pdf · doi:10.48550/arxiv.1410.3564
8 pages, 3 figures
arxiv created 2014/10/14 · openalex publication_date 2014/10/14 · arxiv updated 2014/10/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present randomized versions of the \it triangle algorithm introduced in \citekal14. The triangle algorithm tests membership of a distinguished point p ∈ ℝ m in the convex hull of a given set S of n points in ℝm. Given any \it iterate p' ∈ conv(S), it searches for a \it pivot, a point v ∈ S so that d(p',v) ≥ d(p,v). It replaces p' with the point on the line segment p'v closest to p and repeats this process. If a pivot does not exist, p' certifies that p \not ∈ conv(S). Here we propose two random variations of the triangle algorithm that allow relaxed steps so as to take more effective steps possible in subsequent iterations. One is inspired by the \it chaos game known to result in the Sierpinski triangle. The incentive is that randomized iterates together with a property of Sierpinski triangle would result in effective pivots. Bounds on their expected complexity coincides with those of the deterministic version derived in \citekal14.