PROBING CONVEX POLYGONS WITH HALF-PLANES

被引：15

作者：

SKIENA, SS ^{[1
]}

机构：

[1] SUNY STONY BROOK,DEPT COMP SCI,STONY BROOK,NY 11794

来源：

JOURNAL OF ALGORITHMS | 1991年 / 12卷 / 03期

关键词：

D O I：

10.1016/0196-6774(91)90009-N

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A half-plane probe through a polygon measures the area of intersection between a half-plane and the polygon. We develop techniques based on X-ray probing to determine convex n-gons in 7n + 7 half-plane probes. We also show n + 1 half-plane probes are sufficient to verify a specified convex polygon and prove linear lower bounds for determination and verification. © 1991.

引用

页码：359 / 374

页数：16

共 13 条

[1]

ALEVIZOS PD, IN PRESS J SYMBOLIC

[2] DETERMINING THE SHAPE OF A CONVEX N-SIDED POLYGON BY USING 2N+K TACTILE PROBES [J].