半平面交的新算法及其实用价值.docx

《半平面交的新算法及其实用价值.docx》由会员分享，可在线阅读，更多相关《半平面交的新算法及其实用价值.docx（10页珍藏版）》请在三一办公上搜索。

1、半平面交的新算法及其实用价值 Keywords: Half-plane, Intersection, Feasible Region, Algorithm, Polygon, PracticalAbstract主旨:半平面的交是当今学术界热烈讨论的问题之一，本文将介绍一个全新的O(nlogn)半平面交算法，强调它在实际运用中的价值，并且在某种程度上将复杂度下降至O(n)线性。最重要的是，我将介绍的算法非常便于实现.1 introduces what half-plane intersection is. 2 prepares a linear algorithm for convex poly

2、gon intersection (abbr. CPI). Equipped with such knowledge, a common solution for HPI is briefly discussed in 3. Then, my new algorithm emerges in 4 detailedly. Not only as a conclusion of the whole paper, 5 also discuss its further usage practically and compares it with the older algorithm describe

3、d in 3.1什么是半平面交. 2凸多边形交预备知识. 3简要介绍旧D&C算法. 4揭开我的新算法S&I神秘面纱. 5总结和实际运用.Timestamps: Came up with it in April 2005; implemented partly in June 2005 The sub-problem of HPI appeared in USA Invitational Computing Olympiad contest.; problem set in July 2005 Set an HPI problem in Peking University Online Judg

4、e, with brief introduction about the algorithm.; publicized as a post in USENET, November 6, 2005 URL: .1. IntroductionA line in plane is usually represented as ax+by=c. Similarly, its inequality form ax+byc represents a half-plane (also named h-plane for short) as one side of this line. Notice that

5、 ax+byc and -ax-by-c show opposite h-planes unlike ax+by=c and -ax-by=-c. Half-Plane Intersection (abbr. HPI) considers the following problem:众所周知，直线常用ax+by=c表示，类似地半平面以ax+by()c为定义。Given n half-planes, aix+biyci (1in), you are to determine the set of all points that satisfying all the n inequations.

6、给定n个形如aix+biyci的半平面，找到所有满足它们的点所组成的点集As ! . describes, the feasible region, which is the intersection, forms a shape of convex hull but possibly unbounded. However, we shall add four h-planes forming a rectangle, which is large enough to make sure the area after intersections finite. In the following

7、 sections, we suppose the feasible region is bounded with a finite area.合并后区域形如凸多边形，可能无界。此时增加4个半平面保证面积有限! . (a) (b) Each h-plane builds up at most one side of the convex polygon, hence, the convex region will be bounded by at most n edges. Pay attention the intersection sometimes yields a line, a ra

8、y, a line-segment, a point or an empty region. 每个半平面最多形成相交区域的一条边，因此相交区域不超过n条边。注意相交后的区域，有可能是一个直线、射线、线段或者点，当然也可能是空集。2. Convex Polygon Intersection (abbr. CPI)Intersecting two convex polygons A and B into a single one, can be properly solved via Line Segment Intersection in O(nlogn) time, when there ar

9、e O(n) edges. We will sketch out an easier and more efficient way, named plane sweep method.求两个凸多边形A和B的交（一个新凸多边形）。我们描绘一个平面扫描法。The main idea is to calculate intersections of edges as cutting points, and break boundaries of A and B, into outer edges and inner edges. The segments of inner edges establi

10、sh ties to each other, and form the shape of a polygon, which is the expected polygon after intersection. In ! ., inner edges are indicated by thick segments, which form a bold outline of the intersection. 主要思想: 以两凸边形边的交点为分界点，将边分为内、外两种。内边互相连接，成为所求多边形。Suppose there is a vertical sweep line, performin

11、g left-to-right sweep. The x-coordinates to be swept are called x-events. At anytime, there are at most four intersections from sweep line to either given polygon Assume there is no edge in polygons parallel to the sweep line. If such situation happens, we could rotate the plane in proper angle, or

12、else, we need good sense to judge a great many special cases.:假设有一个垂直的扫描线，从左向右扫描。我们称被扫描线扫描到的x坐标叫做x事件。任何时刻，扫描线和两个多边形最多4个交点l to the upper hull of A (name that intersection Au for short)l to the lower hull of A (name that intersection Al for short)l to the upper hull of B (name that intersection Bu for

13、 short)l to the lower hull of B (name that intersection Bl for short)BuAuBlAlSweep linePolygon APolygon B! .Look at ! ., the lower one between intersections Au and Bu, and the upper one between intersections Al and Bl, form an interval of the current inner region the red segment in bold. Au、Bu中靠下的，和

14、Al、Bl中靠上的，组成了当前多边形的内部区域。Obviously, the sweep line may not go through all the x-event with rational coordinates. Call the edges where Au, Al, Bu and Bl are: e1, e2, e3 and e4 respectively. The next x-event should be chosen among four endpoints of e1, e2, e3 and e4, and four potential intersections: e

15、1e3, e1e4, e2e3 and e2e4.当然，我们不能扫描所有有理数！称Au, Al, Bu, Bl所在的边叫做e1,e2,e3,e4，下一个x事件将在这四条边的端点，以及两两交点中选出。The above operation could be implemented with O(n) running time, since there are O(n) x-events, and the maintenance of Au, Al, Bu and Bl takes only O(1).3. Common solution:Divide-and-Conquer Algorithm

16、(abbr. D&Q)The basic approach is simple, depends on divide-and-conquer idea.l Divide: Partition the n h-planes into two sets of size and .l Conquer: Compute the feasible region (intersection) recursively of both two sub-sets.l Combine: Compute the intersection of two convex polygons, by linear CPI a

17、lgorithm described in 2.l 分: 将n个半平面分成两个n/2的集合.l 治: 对两子集合递归求解半平面交.l 合: 将前一步算出来的两个交(凸多边形)利用第2章的CPI求解.The total time complexity of the solution can be calculated via recursive equation: 总时间复杂度可以用递归分析法.4. My New Solution:Sort-and-Incremental Algorithm (abbr. S&I)Definition of h-planes polar angle:l for

18、the h-plane like x-yconstant, we define its polar angle to .l for the h-plane like x+yconstant, we define its polar angle to .l for the h-plane like x+yconstant, we define its polar angle to -.l for the h-plane like x-yconstant, we define its polar angle to -.半平面的极角定义: 比如x-y常数的半平面，定义它的极角为.-! .Defini

19、tion of h-planes constant:l for the h-plane like ax+byc, we say its constant is c.My new Sort-and-Incremental Algorithm seems lengthy since I am going to introduce it in details:Step 1: 将半平面分成两部分，一部分极角范围(-, ，另一部分范围(-, -(, ! .Step 2:考虑(-, 的半平面(另一个集合类似地做Step3/4)，将他们极角排序。对极角相同的半平面，根据常数项保留其中之一。! .! .! .

20、! .! .! .! .Step 3: 从排序后极角最小两个半平面开始，求出它们的交点并且将他们押入栈。每次按照极角从小到大顺序增加一个半平面，算出它与栈顶半平面的交点。如果当前的交点在栈顶两个半平面交点的右边，出栈（pop）。前问我们说到出栈，出栈只需要一次么？Nie!我们要继续交点检查，如果还在右边我们要继续出栈，直到当前交点在栈顶交点的左边。Step 4:相邻半平面的交点组成半个凸多边形。我们有两个点集，(-, 给出上半个，(-, -(, 给出下半个初始时候，四个指针p1, p2, p3 and p4 指向上/下凸壳的最左最右边。p1, p3向右走，p2, p4向左走。任意时刻，如果最左

21、边的交点不满足p1/p3所在半平面的限制，我们相信这个交点需要删除。p1或p3走向它右边的相邻边。类似地我们处理最右边的交点。重复运作直到不再有更新出现迭代。upper hulllower hullp3p4p1p2! .(a)p3p4p1p2(b)p3p4p2(c)p1p3p4p2(d)p1p3p4p2(e)p1p3p4p2(f)p1*! .no intersection for lower hull除了Step2中的排序以外，S&I算法的每一步都是线性的。通常我们用快速排序实现Step2，总的时间复杂度为O(nlogn)，隐蔽其中的常数因子很小5. Practical Value and L

22、inear approachGreat ideas need landing gear as well as wings. S&I算法似乎和D&C算法时间复杂度相同，但是它有着压倒性(overwhelming)的优势。l 新的S&I算法代码容易编写，相对于D&C大大简单化，C+程序语言实现S&I算法仅需3KB不到.l S&I算法复杂度中的系数，远小于D&C，因为我们不再需要O(nlogn)次交点运算. 通常意义上来讲，S&I程序比D&C快五倍。Remark: intersection calculations play the most important role in both algor

23、ithms due to its operational speed (so slow, equivalent to hundreds of addition operations). CPI, the preparative algorithm which will be called several times from D&C, requires O(n) number of calculations, wherefore it rises the total running time up. Besides, S&I calculates O(n) times in any case.

24、l 如果给定半平面均在(-, （或任意一个跨度为的区间），S&I算法可被显著缩短，C+程序只需要约二十行。USAICO比赛中就出现了这样一题。Asymptotical Optimization to linear: The bottleneck of this algorithm is sorting. Pay attention the sorting is NOT a comparison sort (sorting based on comparison)! The key words for elements to be sorted are polar angles, which c

25、an be certainly determined by gradient a decimal fraction. Since then, we can replace the O(nlogn) quick-sort to O(n) radix-sort. The asymptotical complexity of algorithm can decrease to O(n). Anyway O(n) approach usually runs slower than nlogn ones for its additional memory usage!本算法瓶颈是排序，这里的排序不是比较

26、排序，因此可以将快速排序替换成基数排序，降低程序渐进时间复杂度到线性。The sentiment of my creation: An invention does not attribute to someone who comes up with ideas. Most people have ideas. The difference between the average person and the inventor is that the inventor for some reason believes only himself, and has the urge to see

27、his ideas through to fruition. Henri Matisse, a French painter and sculptor, ever said there is nothing more difficult for a truly creative painter than to paint a rose, because before he can do so, he has first to forget all the roses that were ever painted. Equipped with both idealistic and practi

28、cal spirit of innovation, I am on the way. How about you?Bibliography1. Kurt Mehlhorn. Data Structures and Algorithms Vol 3. Springer-Verlag, New York, 1984.2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to algorithms 2nd Edition. MIT Press, New York, 20013. Gill Barequet. Computational Geometry Lecture 4, Spring 2004/2005.4. Kavitha Telikepalli. Algorithms and Data Structures, Lecture 3, Winter 2003/2004.9