Probing convex polygons with X-Rays Journal Article


Author(s): Edelsbrunner, Herbert; Skiena, Steven S
Article Title: Probing convex polygons with X-Rays
Affiliation
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.
Journal Title: SIAM Journal on Computing
Volume: 17
Issue 5
ISSN: 0097-5397
Publisher: SIAM  
Date Published: 1988-01-01
Start Page: 870
End Page: 882
Copyright Statement: Copyright © 1988 © Society for Industrial and Applied Mathematics
DOI: 10.1137/0217054
Open access: no
IST Austria Authors