There are several algorithms to compute the lower convex hull of a set of points in the plane, with different trade-offs in terms of runtime complexity and ease of implementation. Here are some of the most popular ones:

    Andrew's Algorithm: This is a sweep line algorithm that sorts the points by their x-coordinate, and then scans the points from left to right while maintaining a monotone chain. The monotone chain is updated using binary search, which takes O(log n) time, where n is the number of points in the chain. The overall time complexity of the algorithm is O(n log n).

    Graham's Scan: This is another sweep line algorithm that sorts the points by their polar angle with respect to the leftmost point. The algorithm then scans the points in order, and removes points from the stack if they create a non-convex angle. The time complexity of the algorithm is O(n log n).

    Chan's Algorithm: This is an improvement on Graham's scan that uses a divide-and-conquer approach to sort the points by their polar angle. The algorithm takes O(n log n) time, and has a better constant factor than Graham's scan, which makes it faster in practice for large inputs.

    Jarvis March (also known as Gift Wrapping): This is an incremental algorithm that starts from the leftmost point and repeatedly finds the point that is closest to the current hull. The algorithm takes O(n^2) time in the worst case, but can be optimized to take O(n log n) time by using a binary search tree to find the closest point.

    QuickHull: This is a divide-and-conquer algorithm that starts by finding the extreme points (the leftmost, rightmost, topmost, and bottommost points), and then recursively divides the set of points into two convex hulls. The time complexity of the algorithm is O(n log n) on average, and O(n^2) in the worst case.

In terms of efficiency, the most efficient algorithms are Andrew's, Graham's and Chan's, with a time complexity of O(n log n). The Jarvis March and QuickHull algorithms are also viable options, but their worst-case time complexity is higher, at O(n^2).
มีอัลกอริธึมหลายอย่างในการคำนวณส่วนนูนด้านล่างของชุดจุดในระนาบ โดยมีข้อดีข้อเสียที่แตกต่างกันในแง่ของรันไทม์ที่ซับซ้อนและความง่ายในการใช้งาน ต่อไปนี้คือตัวอย่างที่ได้รับความนิยมมากที่สุด: อัลกอริทึมของแอนดรูว์: นี่คืออัลกอริธึมเส้นกวาดที่เรียงลำดับจุดตามพิกัด x จากนั้นจะสแกนจุดจากซ้ายไปขวาโดยยังคงความต่อเนื่องแบบโมโนโทนไว้ โมโนโทนเชนได้รับการอัปเดตโดยใช้การค้นหาแบบไบนารี่ ซึ่งใช้เวลา O(log n) โดยที่ n คือจำนวนจุดในเชน ความซับซ้อนของเวลาโดยรวมของอัลกอริทึมคือ O(n log n) การสแกนของเกรแฮม: นี่เป็นอีกอัลกอริธึมเส้นกวาดที่เรียงลำดับจุดตามมุมเชิงขั้วเทียบกับจุดซ้ายสุด จากนั้นอัลกอริทึมจะสแกนจุดตามลำดับ และลบจุดออกจากสแต็กหากสร้างมุมที่ไม่นูน ความซับซ้อนของเวลาของอัลกอริทึมคือ O(n log n) อัลกอริทึมของ Chan: นี่เป็นการปรับปรุงการสแกนของ Graham ที่ใช้วิธีการแบ่งและพิชิตเพื่อจัดเรียงจุดตามมุมเชิงขั้ว อัลกอริธึมใช้เวลา O(n log n) และมีปัจจัยคงที่ที่ดีกว่าการสแกนของ Graham ซึ่งทำให้ในทางปฏิบัติเร็วขึ้นสำหรับอินพุตขนาดใหญ่ Jarvis March (หรือเรียกอีกอย่างว่าการห่อของขวัญ): นี่เป็นอัลกอริธึมส่วนเพิ่มที่เริ่มจากจุดซ้ายสุดและค้นหาจุดที่ใกล้กับตัวถังปัจจุบันมากที่สุดซ้ำแล้วซ้ำเล่า อัลกอริธึมใช้เวลา O(n^2) ในกรณีที่เลวร้ายที่สุด แต่สามารถปรับให้เหมาะสมเพื่อใช้เวลา O(n log n) ได้โดยใช้แผนผังการค้นหาแบบไบนารีเพื่อค้นหาจุดที่ใกล้เคียงที่สุด QuickHull: นี่คืออัลกอริธึมการแบ่งแล้วพิชิตซึ่งเริ่มต้นด้วยการค้นหาจุดสูงสุด (จุดซ้ายสุด ขวาสุด บนสุด และล่างสุด) จากนั้นจึงแบ่งชุดของจุดออกเป็นสองส่วนนูนแบบวนซ้ำ ความซับซ้อนของเวลาของอัลกอริทึมคือ O(n log n) โดยเฉลี่ย และ O(n^2) ในกรณีที่เลวร้ายที่สุด ในแง่ของประสิทธิภาพ อัลกอริธึมที่มีประสิทธิภาพมากที่สุดคือ Andrew's, Graham's และ Chan's โดยมีเวลาซับซ้อนเท่ากับ O(n log n) อัลกอริธึม Jarvis March และ QuickHull ก็เป็นตัวเลือกที่ใช้งานได้เช่นกัน แต่ความซับซ้อนของเวลาที่แย่ที่สุดจะสูงกว่าที่ O(n^2)
spam fails_task lang_mismatch pii not_appropriate hate_speech sexual_content quality toxicity humor helpfulness creativity violence