平面凸多边形斜支撑线求解的最佳算法

鄢勇; 金灿明

您当前的位置：

首页 >

文章列表页 >

平面凸多边形斜支撑线求解的最佳算法

更新时间：2025-12-08

- 平面凸多边形斜支撑线求解的最佳算法
- Optimal Algorithm for Searching the Supporting Lines of Two Planar Convex Ploygons
- 电子学报 1994年第5期
- 作者机构：
  
  华中理工大学计算机系
- 作者简介：
- 基金信息：
- DOI：
  中图分类号： O24
- 纸质出版：1994
- 稿件说明：
移动端阅览
[1]鄢勇,金灿明.平面凸多边形斜支撑线求解的最佳算法[J].电子学报,1994(05):9-14+19.

鄢勇, 金灿明. Optimal Algorithm for Searching the Supporting Lines of Two Planar Convex Ploygons[J]. Acta Electronica Sinica, 1994, (5).
[1]鄢勇,金灿明.平面凸多边形斜支撑线求解的最佳算法[J].电子学报,1994(05):9-14+19. DOI：

鄢勇, 金灿明. Optimal Algorithm for Searching the Supporting Lines of Two Planar Convex Ploygons[J]. Acta Electronica Sinica, 1994, (5). DOI：

摘要

平面凸多边形斜支撑求解是计算几何中诸多问题的一个核心算法．至今，求解该问题的最好算法的时间复杂度为Ｏ（ｎ＋ｍ）．本文在巧妙利用凸多边形特殊性质的基础上，给出了一时间复杂度为Ｏ（ｌｏｇ（ｎ＋ｍ））的最佳算法，从而彻底解决了这一问题．

Abstract

The algorithm for finding the supporting line of two planar ploygons is a kernal algorithm in many computation geometry problems and has found wider applications in computer graphics and robotics.So far

the computation complexity of the best algorithm for this problem is O（n+m）. In this paper

with the help of the properties of the convex ploygons

a fast algorithm with time complexity O（log （n+m ））is presented and is proved to be optimal in the range of constant factors.

关键词

Keywords

references

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

可变环境下基于位姿变换矩阵的机器人无标定手眼协调方法

基于计算几何的非线性可视化分类器设计

一种基于切割映射的规则冲突消除算法

一个保护私有信息的多边形相交判定协议

保护私有信息的图形相似判定