什么是最小凸集(如何确定,如何画图)如今使用天然气的人越来越多,作为天然气的供应商如何向用户供气,即如何使用户之间连接成一个树形网络是很重要的.一般来说,我们假设任意两个用户之

Question

什么是最小凸集(如何确定,如何画图)
如今使用天然气的人越来越多,作为天然气的供应商如何向用户供气,即如何使用户之间连接成一个树形网络是很重要的.一般来说,我们假设任意两个用户之间存在直线道相连,但是在连接过程中,有些区域是必须绕开的,这些必须绕开的区域我们称为障碍区域.
表1给出了若干个可能的用户的地址的横纵坐标,可能的用户的含义是：如果用户的地址不在障碍区域内,那么该用户就是需要使用天然气的用户（即有效用户）,否则如果用户的地址在障碍区域内,那么该用户就是无效用户（即不要将该用户连接在网络中）.
表2-表5是分别是4个障碍区域必须要覆盖的点的坐标,而对应障碍区域就是覆盖这些要覆盖的点的最小凸集.
请您判定表1中那些用户为有效用户.
请您设计一个算法将有效用户连接起来,并且连接的距离总和最小

Answer 1

最小凸集就是说通过一个平面的点集,通过一个最小的凸多边形覆盖,这个多边形的顶点必然属于原来的点集,然后这些顶点的集合就是最小凸集