Probing convex polygons with X-Rays
Edelsbrunner H, Skiena S. 1988. Probing convex polygons with X-Rays. SIAM Journal on Computing. 17(5), 870–882.
Download
No fulltext has been uploaded. References only!
DOI
Journal Article
| Published
| English
Scopus indexed
Author
Edelsbrunner, HerbertISTA 
;
Skiena, Steven
;
Skiena, StevenAbstract
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.
Publishing Year
Date Published
1988-01-01
Journal Title
SIAM Journal on Computing
Publisher
SIAM
Acknowledgement
The research of this author was supported by the Amoco Foundation Facility for the Development of Computer Science 1-6-44862.
Volume
17
Issue
5
Page
870 - 882
ISSN
eISSN
IST-REx-ID
Cite this
Edelsbrunner H, Skiena S. Probing convex polygons with X-Rays. SIAM Journal on Computing. 1988;17(5):870-882. doi:10.1137/0217054
Edelsbrunner, H., & Skiena, S. (1988). Probing convex polygons with X-Rays. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0217054
Edelsbrunner, Herbert, and Steven Skiena. “Probing Convex Polygons with X-Rays.” SIAM Journal on Computing. SIAM, 1988. https://doi.org/10.1137/0217054 .
H. Edelsbrunner and S. Skiena, “Probing convex polygons with X-Rays,” SIAM Journal on Computing, vol. 17, no. 5. SIAM, pp. 870–882, 1988.
Edelsbrunner H, Skiena S. 1988. Probing convex polygons with X-Rays. SIAM Journal on Computing. 17(5), 870–882.
Edelsbrunner, Herbert, and Steven Skiena. “Probing Convex Polygons with X-Rays.” SIAM Journal on Computing, vol. 17, no. 5, SIAM, 1988, pp. 870–82, doi:10.1137/0217054 .
Google Scholar