Skip to main navigation Skip to search Skip to main content

Probing convex polygons with X-rays

Research output: Contribution to journalArticlepeer-review

40 Scopus citations

Abstract

An X-ray probe through a polygon measures the length of intersection between a line and the polygon. This paper considers the properties of various classes of X-ray probes, and shows how they interact to give finite strategies for completely describing convex n-gons. It is shown that (3n/2)+6 probes are sufficient to verify a specified n-gon, while for determining convex polygons (3n-1)/2 X-ray probes are necesssary and 5n+O(1) sufficient, with 3n+O(1) sufficient given that a lower bound on the size of the smallest edge of P is known.

Original languageEnglish
Pages (from-to)870-882
Number of pages13
JournalSIAM Journal on Computing
Volume17
Issue number5
DOIs
StatePublished - 1988

Fingerprint

Dive into the research topics of 'Probing convex polygons with X-rays'. Together they form a unique fingerprint.

Cite this