August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
用算法的眼光去看问题
｜
11
用算法的眼光
去看问题
1.3.3 并行算法
如果条件允许，使用多个处理器来计算凸包也是一种可行的办法，即将点集按照
x
坐标
分成多个子集，然后使用各个处理器计算单个子集的凸包。一旦所有处理器完成了子凸
包的计算，就可以通过不断合并相邻子凸包来
拼凑
出最终的凸包得到。并行计算可以将
子问题分配给多个处理器来加快整个解决方案的执行。
图
1-5
展示了使用
3
个处理器计算凸包的情况，两个相邻的凸包可以通过加两条切线完
成拼接，其中一条切线在顶部，另一条切线在底部。最后，删除这两条切线组成的四边
形所包含的线段即可。
图 1-5：通过并行构造和衔接得到凸包
1.3.4 近似算法
即使有了这些优化，计算凸包算法所固有的下界性能问题仍未有突破。不过，与其计算
出精确解，也许近似解就足够了——近似解不但可以很快地计算出来，而且误差也是
能
够精确测定的
。
Bentley-Faust-Preparata
算法可以通过将点集切分成多个纵向区域来构建一个近似凸包
（
Bentley et al.
，
1982
）。在每个区域中，可以很容易找到最大点（根据
y
坐标决定）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.