Probing convex polygons with X-Rays

H. Edelsbrunner, S. Skiena, SIAM Journal on Computing 17 (1988) 870–882.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
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.
Publishing Year
Date Published
1988-01-01
Journal Title
SIAM Journal on Computing
Volume
17
Issue
5
Page
870 - 882
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, 17(5), 870–882. https://doi.org/10.1137/0217054
Edelsbrunner, Herbert, and Steven Skiena. “Probing Convex Polygons with X-Rays.” SIAM Journal on Computing 17, no. 5 (1988): 870–82. 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, 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 .

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar