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 language | English |
|---|---|
| Pages (from-to) | 870-882 |
| Number of pages | 13 |
| Journal | SIAM Journal on Computing |
| Volume | 17 |
| Issue number | 5 |
| DOIs | |
| State | Published - 1988 |
Fingerprint
Dive into the research topics of 'Probing convex polygons with X-rays'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver