Skip to main navigation Skip to search Skip to main content

Probing convex polygons with half-planes

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)359-374
Number of pages16
JournalJournal of Algorithms
Volume12
Issue number3
DOIs
StatePublished - Sep 1991

Cite this