任意多边形的最小外接圆(注意最小两字）通常的外接圆是讲得是所有顶点在圆上,不存在最小两字,地图上存在N个点,我想用一个最小的圆将其全部圈起来,怎么求,给数学算法就行.

题目详情

任意多边形的最小外接圆(注意最小两字）
通常的外接圆是讲得是所有顶点在圆上,不存在最小两字,地图上存在N个点,我想用一个最小的圆将其全部圈起来,怎么求,给数学算法就行.

▼优质解答

答案和解析

这是离散几何问题.具体是这样做的:
多边形可不妨设为凸的,因为显然有凹多边形跟其凸包多边形的最小外接圆相同.算法上可以先求出给定多边形的凸包.
设P是一个给定的凸n边形.考察其任意三个顶点决定的圆,至多有{n choose 3}个不同的圆.
设这些圆中能盖住P的为圆C_1,圆C_2,...,圆C_m.
找出那个最小的圆C_i即可,这里谁大谁小看直径,最小的C_i可能不唯一.

看了任意多边形的最小外接圆(注意...的网友还看了以下：

一个简单的思想品德问题：“责任是一个人应当做的事情.责任是不应该做某些事情.”归纳成一句话,要把在　2020-04-07 …

下面四个命题中,正确的有1.经过三点可以确定一个圆2.任意一个三角形都有一个外接圆,而且只有一个外　2020-04-27 …

在盒内有一个有电源，一只电铃和若干导线组成的电路，盒外有abcd四个接线柱，若用导线将ad连接或b 　2020-05-13 …

给出下列说法：①经过三点一定可以作圆；②任何一个三角形一定有一个外接圆，而且只有一个外接圆；③任意　2020-05-16 …

一个自然数减去57后是一个完全平方数,这个自然数加上123后任是一个完全平方数,试求这个自然数急　2020-05-16 …

三相发电机采用三角形连接时任意两个连接点的电压是多少?三相发电机采用三角形连接时用电压表测量任意两　2020-05-17 …

有难度的仿写句子责任是一块砖,今天看起来微不足道,但它却垫起了每个人明天的一段高度.责任是一个路标　2020-06-13 …

无主之地2联机任务问题甲玩家接了一个任务，乙在单机时也接了相同的，任务都是一个进度，完成任务后，乙　2020-06-17 …

责任伴我成长（8分）“责任是一块砖，今天看起来微不足道，但它却垫起了每个人明天的一段高度；责任是一　2020-06-18 …

朝阳社区有3个居委会,每个居委会有2个主任,每次社区开会只要一个主任参加,第一次到会的有A、E、F 　2020-06-20 …