英文:
Algorithm: Polygon max element in O(log n)
问题
我想找到凸多边形中具有最大 x 轴值的顶点。
多边形是凸多边形且是随机的。
其顶点以数组形式表示，格式为：(x，y)。
从笛卡尔坐标系转换为数组的顺序是逆时针顺序的。
x 轴上最左边的顶点是数组的第一个元素。
我需要找到在 x 轴上最右边的顶点（具有最大的 x 值）的最有效方法。
我的想法是：
如果顶点是凸多边形，那么数组中必须有两个有序的区间，比方说从索引 0 到索引 “s” 和从索引 “s” 到最后一个索引。第一个区间是增加的，第二个是减少的 - 第一个是多边形的下部分，第二个是上部分。
（我不确定这种假设在任何情况下都是正确的）
然后，我知道索引为 “s” 的元素具有最大的 x 值。
现在，我可以使用稍微修改过的二分查找来找到“s”索引上的元素（在每个周期内决定中间元素是在第一个区间还是第二个区间，然后执行二分查找的操作...）。
有人能告诉我我的想法是否正确吗？谢谢。
英文:
I want to find the vertice in convex polygon, which has the greatest x axis value.
The polygon is convex and random.
Its vertices are represented in array as tuples: (x,y).
The vertices from cartesian coordinate system to array are ordered in counterclockwise order.
The most left vertice on the x axis is the first element in the array.
I need to figure out the most efficient approach to find the most right vertice on the x axis (has greatest x value).
My idea:
If the vertice is convex, then in the array must be 2 ordered intervals, lets say from index 0 to index “s” and from index “s” to the last index. 1st interval is increasing the 2nd is decreasing - 1st is lower part of polygon, 2nd uppper.
(Im not sure if this assumotion is correct in any case)
Then I know that the “s” indexed element is the one with greatest x value.
Now i can use slightly modified binary search to find element on the “s” index (in each cycle decide if the middle element is in the 1st interval or the 2nd one and then do the binary search stuff..).
Can anyone tell me if my idea is right? Thank you
答案1
得分: 2
当你从任意顶点开始迭代顶点时，你将得到一个具有单个内部局部极值的序列（即，该序列将在查找的顶点之前递增，然后递减，然后可能会再次递增直到结束）。形状将类似于这样：
/\
/ \/
/
还有一些特殊情况需要考虑：
- 如果存在多个具有最大x值的顶点（在这种情况下，它们将紧随在一起，因此可以进行简单的检查）
- 如果你从最佳顶点开始，形状将更像
\/。要考虑这一点，比较第一个/最后一个顶点的x值与你找到的值。
无论如何，你寻找的解决方案的基础可以是三分搜索（或在geeksforgeeks中）或爬山算法。这两种方法都可以实现log(n)的目标。
英文:
When you iterate the vertices starting from an arbitrary vertex you will get a sequence that has a single internal local extremum (i.e. the sequence will be increasing until the vertex you are looking for, then decreasing and potentially then it will start increasing until the end). The shape will resemble something like this:
/\
/ \/
/
there are few edge cases to consider too:
- if there is more than one vertex with max x value (in that case they will be right after one another, so you can do a simple check)
- if you start from the optimal vertex, the shape will be more like
\/. To account for that compare the x value of the first/last vertex with what you find
Either way the basis of the solution you are looking for could be ternary search (or in geeksforgeeks) or hill climbing. Both will be able to achieve the log(n) target.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论