ในการวิเคราะห์อัลกอริทึมผู้เขียนหลายท่านได้ศึกษาการคำนวณปริมาตร ของ ทรงนูนมิติสูงซึ่งเป็นปัญหาที่สามารถใช้เป็นแบบจำลองสำหรับปัญหาอื่นๆ ในการแจงนับเชิงคอมบินา ทอริก ได้เช่นกัน บ่อยครั้งที่งานเหล่านี้ใช้แบบจำลองกล่องดำในการคำนวณ โดยที่อินพุตจะได้รับจากรูทีนย่อยสำหรับการทดสอบว่าจุดนั้นอยู่ภายในหรือภายนอกทรงนูน แทนที่จะเป็นรายการจุดยอดหรือหน้าของทรงหลายเหลี่ยมนูน อย่างชัดเจน เป็นที่ทราบกันดีว่าในแบบจำลองนี้ ไม่มีอัลกอริทึมเชิงกำหนดใดที่สามารถให้ค่าประมาณที่แม่นยำได้^{[ 1 ] [ 2 ]}และแม้แต่รายการหน้าหรือจุดยอดอย่างชัดเจน ปัญหาก็ยังเป็นปัญหา#P-hard [ ^{3 ] อย่างไรก็ตาม} งานร่วมกันของMartin Dyer , Alan M. FriezeและRavindran Kannanได้นำเสนอแผนการประมาณค่าแบบพหุนามเวลาแบบ สุ่ม สำหรับปัญหานี้ ซึ่งแสดงให้เห็นถึงความแตกต่างอย่างชัดเจนระหว่างความสามารถของอัลกอริทึมแบบสุ่มและเชิงกำหนด^{[ 4 ]}

ผลลัพธ์หลักของบทความนี้คืออัลกอริทึมแบบสุ่มสำหรับการหาค่าประมาณของปริมาตรของทรงนูนในปริภูมิยูคลิดมิติ โดยสมมติว่ามีออราเคิล สมาชิกอยู่ อั ลกอริทึมนี้ใช้เวลาที่จำกัดด้วยพหุนามในมิติของและอัลกอริทึมนี้ผสมผสานแนวคิดสองอย่างเข้าด้วยกัน: ${\displaystyle \varepsilon }$${\displaystyle K}$${\displaystyle n}$${\displaystyle n}$${\displaystyle K}$${\displaystyle 1/\varepsilon }$

• โดยการใช้ วิธีการ Markov chain Monte Carlo (MCMC) สามารถสร้างจุดที่มีการกระจายแบบสุ่มเกือบสม่ำเสมอภายในวัตถุทรงนูนที่กำหนดได้ โครงร่างพื้นฐานของอัลกอริทึมคือการสุ่มตัวอย่างแบบเกือบสม่ำเสมอจากภายในโดยการวางตารางที่ประกอบด้วยลูกบาศก์มิติ n และทำการเดินแบบสุ่มบนลูกบาศก์เหล่านี้ โดยใช้ทฤษฎีของMarkov chain ที่ผสมอย่างรวดเร็วพวกเขาแสดงให้เห็นว่าต้องใช้เวลาพหุนามสำหรับการเดินแบบสุ่มที่จะเข้าสู่สภาวะการกระจายแบบเกือบสม่ำเสมอ^{[ 4 ]}${\displaystyle K}$${\displaystyle n}$
• การใช้การสุ่มตัวอย่างแบบปฏิเสธ (Rejection Sampling ) ทำให้สามารถเปรียบเทียบปริมาตรของทรงนูนสองทรงที่ซ้อนกันอยู่ได้ เมื่อปริมาตรของทั้งสองทรงนั้นแตกต่างกันเพียงเล็กน้อย หลักการพื้นฐานคือการสร้างจุดสุ่มขึ้นภายในทรงนูนด้านนอกของทั้งสองทรง แล้วนับว่าจุดเหล่านั้นปรากฏอยู่ภายในทรงนูนด้านในบ่อยแค่ไหน

วัตถุทรงนูนที่กำหนดให้สามารถประมาณได้ด้วยลำดับของวัตถุที่ซ้อนกันหลายชั้น จนกระทั่งได้วัตถุที่มีปริมาตรที่ทราบค่า (ทรงกลมหลายมิติ) โดยใช้วิธีนี้ในการประมาณค่าตัวคูณที่ปริมาตรเปลี่ยนแปลงไปในแต่ละขั้นของลำดับดังกล่าว การคูณตัวคูณเหล่านี้จะให้ปริมาตรโดยประมาณของวัตถุเดิม

ผลงานนี้ทำให้ผู้เขียนได้รับรางวัลฟุลเคอร์สันประจำปี 1991 ^{[ 5 ]}

แม้ว่าเวลาของอัลกอริทึมนี้จะเป็นแบบพหุนาม แต่ก็มีเลขชี้กำลังสูง ผู้เขียนคนต่อมาได้ปรับปรุงเวลาการทำงานของวิธีนี้โดยให้การผสมลูกโซ่ Markov ที่รวดเร็วยิ่งขึ้นสำหรับปัญหาเดียวกัน^{[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ]}

ผลลัพธ์การประมาณค่าในเวลาพหุนามได้รับการขยายไปสู่โครงสร้างที่ซับซ้อนมากขึ้น เช่น การรวมและการตัดกันของวัตถุ^{[ 11 ]}ซึ่งเกี่ยวข้องกับ ปัญหาการวัด ของ Klee