ขั้นตอนวิธีเคิร์กแพทริก–ไซเดิล

ขั้นตอนวิธีเคิร์กแพทริก–ไซเดิล  หรือเรียกอีกชื่อว่า "ขั้นตอนวิธีแต่งงานก่อนเอาชนะ" (marriage-before-conquest algorithm) เป็นขั้นตอนวิธีที่ใช้สำหรับคำนวณหา convex hull ของเซทจุดบนระนาบ โดยมีความซับซ้อนด้านเวลา (time complexity) เป็น O("n" log "h") ซึ่ง "n" คือจำนวนจุดนำเข้า และ "h" คือจำนวนขอบของ hull ดังนั้นขั้นตอนวิธีนี้เวลาในการคำนวณจึงขึ้นอยู่กับทั้งขนาดของข้อมูลนำเข้าและข้อมูลส่งออก (output-sensitive algorithm) ชื่อของขั้นตอนวิธีเคิร์กแพทริก–ไซเดิล มาจากชื่อหลังของผู้คิดค้นได้แก่ เดวิด จี. เคิร์กแพทริก (David G. Kirkpatrick) และ ไรมุนด์ ไซเดิล (Raimund Seidel) 
ขั้นตอนวิธี.
ขั้นตอนวิธีที่ใช้หา convex hull แบบเดิมจะใช้ขั้นตอนวิธีการแบ่งแยกและเอาชนะ (divide-and-conquer algorithm) คือการแบ่งจุดที่นำเข้าออกเป็นสองส่วนที่เท่ากัน โดยใช้เส้นแนวตั้งในการแบ่ง และเวียนเกิดหา convex hull ของส่วนย่อยซ้ายและส่วนย่อยขวา จากนั้นนำทั้งสองส่วนย่อยมาผสานกัน ด้วยการหา "bridge edges" ซึ่งก็คือเส้นที่เชื่อมและสัมผัสทั้งสอง hulls จากทั้งด้านบนและด้านล่าง
ขั้นตอนวิธีเคิร์กแพทริก–ไซเดิล นั้นจะมีขั้นตอนกลับลำดับกันกับวิธีแบ่งแยกและเอาชนะ คือหา bridge edges เลยโดยไม่จำเป็นต้องหา convex hull ก่อน ซึ่งในขั้นตอนแรกคือการแบ่งจุดโดยการหาเส้นแบ่งแนวตั้งที่ถูกกำหนดโดยค่ามัธยฐานของพิกัดแกน "x" ของจุดที่นำเข้าทั้งหมด ขั้นตอนต่อไปคือการหาเส้นขอบของ convex hull ที่ตัดกับเส้นแบ่งนั้น ซึ่งขั้นตอนนี้จะใช้เวลาเป็นเชิงเส้น (O("n")) หากจุดบนฝั่งซ้ายหรือฝั่งขวาของเส้นแบ่งที่ไม่ช่วยในการหาเส้นขอบจะถูกละทิ้ง ซึ่งในการหาขอบบนของ convex hull นั้นจุดที่ไม่ช่วยในการหาเส้นขอบและจะถูกละทิ้งคือ จุดที่อยู่ใต้ bridge edge ลงมา ในขณะที่การหาขอบล่างของ convex hull นั้นจุดที่อยู่เหนือ bridge edge ขึ้นไปจะถูกละทิ้ง จากนั้นเวียนเกิดด้วยจุดทางฝั่งซ้ายของเส้นแบ่งที่ยังไม่ถูกละทิ้ง และด้วยจุดทางฝั่งขวาของเส้นแบ่งที่ยังไม่ถูกละทิ้งไปเรื่อยๆ จนกระทั่งได้ขอบของ convex hull ครบทั้งหมด โดยขั้นตอนวิธีนี้จะต้องแยกดำเนินการเพื่อหาขอบบน และขอบล่างของ convex hull อีกครั้ง
การหาเส้นขอบบนในเวลา O("n") นั้นเราจะสมมติให้เส้นขอบมีความชันเป็น "K*" จากนั้นเดาค่าความชัน "K" ขึ้นมาแล้วพยายามคำนวณค่า "K*" โดยเปรียบเทียบกับค่า "K" นั้น ให้ "li" จากนั้นทำการหาเส้นตรงที่มีความชัน "K" และผ่านจุดใดๆ ในเซทของจุดทั้งหมดที่นำเข้า ที่ทำให้ทุกๆ จุดในเซทอยู่ใต้มัน (เส้นนี้จะตัดกับเส้นแบ่งสูงที่สุด) เราสามารถหาเส้นนี้ได้ในเวลา O("n") ถ้าเส้นที่หาได้นี้ผ่านทั้งจุดทางฝั่งซ้ายและฝั่งขวาของเส้นแบ่ง เส้นนี้ก็คือเส้นขอบบนที่เรากำลังหาอยู่ แสดงว่าค่า "K"="K*" แล้ว แต่ถ้าเส้นนี้ผ่านเฉพาะจุดทางฝั่งซ้ายของเส้นแบ่งเท่านั้น แสดงว่าค่า "K">"K*" จึงต้องเดาค่า "K" ใหม่ให้มีค่าที่น้อยลง และถ้าเส้นนี้ผ่านเฉพาะจุดทางฝั่งขวาของเส้นแบ่งเท่านั้น แสดงว่าค่า "K"<"K*" จึงต้องเดาค่า "K" ใหม่ให้มีค่าที่มากขึ้น จนกว่าจะเจอค่า "K" ที่เท่ากับ "K*" ซึ่งก็คือเส้นขอบบนที่หาอยู่ ในการหาเส้นขอบล่างก็ใช้วิธีคล้ายๆ แบบนี้ในการหาเช่นเดียวกัน
ความซับซ้อนด้านเวลา.
ให้ "h" คือจำนวนขอบของ hull ถ้า "h" = 1 ในขั้นของการเวียนเกิดใดๆ แสดงว่าเส้นขอบเชื่อมระหว่างจุดซ้ายสุดและจุดขวาสุด ซึ่งจุดอื่นๆ ถูกละทิ้งไปหมดแล้ว ดังนั้นจึงใช้เวลา O("n")
ถ้าฝั่งซ้ายของเส้นแบ่งมี <math>h_L\,\!</math> ขอบ และฝั่งขวาของเส้นแบ่งมี <math>h_R\,\!</math> ขอบ ดังนั้นจะได้ <math>h = 1 + h_L + h_R\,\!</math> และให้เวลาในการคำนวณของขั้นตอนวิธีนี้อธิบายได้โดย <math>T(n, h)\,\!</math>
<math>T(n, 1) = cn\,\!</math>
<math>T(n, h) = cn + T(\frac {n}{2}, h_L) + T(\frac{n}{2}, h_R)\,\!</math>
ให้ <math>T(m, h') \le cm \log h'</math> เมื่อ <math>m < n\,\!</math> และ <math>1 < h' < h\,\!</math> จะได้ว่า
<math>T(n, h) \le cn + c \frac {n}{2} \log h_L + c \frac{n}{2} \log h_R\,\!</math>
จากนั้นใช้ความจริงที่ว่า <math>\frac {1}{2}(\log h_L + \log h_R) \le \log \frac {h_L + h_R}{2}\,\!</math> จะได้
<math>T(n, h) \le cn + c \frac {n}{2}(2 \log \frac {h_L + h_R}{2}) \le cn + cn(\log (h - 1)) \le cn \log h\,\!</math>
ดังนั้น <math>T(n, h) = O(n \log h)\,\!</math>