Abstract
We consider stabbing regions for a set S of n line segments in the plane, that is, regions in the plane that contain exactly one endpoint of each segment of S. Concretely, we provide efficient algorithms for reporting all combinatorially different stabbing regions for S for regions that can be described as the intersection of axis-parallel halfplanes; these are halfplanes, strips, quadrants, 3-sided rectangles, and rectangles. The running times are O(n) (for the halfplane case), \(O(n\log n)\) (for strips, quadrants, and 3-sided rectangles), and \(O(n^2\log n)\) (for rectangles).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abellanas, M., Hurtado, F., Icking, C., Klein, R., Langetepe, E., Ma, L., Palop, B., Sacristán, V.: Smallest color-spanning objects. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 278–292. Springer, Heidelberg (2001)
Abellanas, M., Hurtado, F., Icking, C., Klein, R., Langetepe, E., Ma, L., Palop, B., Sacristán, V.: The farthest color Voronoi diagram and related problems. In: Proceedings of the 17th European Workshop on Computational Geometry, pp. 113–116 (2001)
Atallah, M., Bajaj, C.: Efficient algorithms for common transversal. Inf. Process. Lett. 25, 87–91 (1987)
Avis, D., Wenger, R.: Polyhedral line transversals in space. Discrete Comput. Geom. 3, 257–265 (1988)
Barba, L., Durocher, S., Fraser, R., Hurtado, F., Mehrabi, S., Mondal, D., Morrison, J., Skala, M., Wahid, M.A.: On \(k\)-enclosing objects in a coloured point set. In: Proc. of the 25th Canadian Conference on Computational Geometry, pp. 229–234 (2013)
Bhattacharya, B.K., Czyzowicz, J., Egyed, P., Toussaint, G., Stojmenovic, I., Urrutia, J.: Computing shortest transversals of sets. In: Proceedings of the 7th Annual Symposium on Computational Geometry, pp. 71–80 (1991)
Bhattacharya, B., Kumar, C., Mukhopadhyay, A.: Computing an area-optimal convex polygonal stabber of a set of parallel line segments. In: Proceedings of the 5th Canadian Conference on Computational Geometry, pp. 169–174 (1993)
Brönnimann, H., Everett, H., Lazard, S., Sottile, F., Whitesides, S.: Transversals to line segments in three-dimensional space. Discrete Comput. Geom. 34, 381–390 (2005)
Claverol, M.: Problemas geométricos en morfología computacional. Ph.D. thesis, Universitat Politècnica de Catalunya (2004)
Claverol, M., Garijo, D., Grima, C.I., Márquez, A., Seara, C.: Stabbers of line segments in the plane. Comput. Geom. Theor. Appl. 44(5), 303–318 (2011)
Das, S., Goswami, P.P., Nandy, S.C.: Smallest color-spanning objects revisited. Int. J. Comput. Geom. Appl. 19(5), 457–478 (2009)
Díaz-Báñez, J.M., Korman, M., Pérez-Lantero, P., Pilz, A., Seara, C., Silveira, R.I.: New results on stabbing segments with a polygon. Comput. Geom. Theor. Appl. 48(1), 14–29 (2015)
Edelsbrunner, H., Maurer, H.A., Preparata, F.P., Rosenberg, A.L., Welzl, E., Wood, D.: Stabbing line segments. BIT 22, 274–281 (1982)
Fogel, E., Hemmer, M., Porat, A., Halperin, D.: Lines through segments in three dimensional space. In: Proceedings of the 29th European Workshop on Computational Geometry, Assisi, Italy, pp. 113–116 (2012)
Goodrich, M.T., Snoeyink, J.S.: Stabbing parallel segments with a convex polygon. In: Proceedings 1st Workshop Algorithms and Data Structures, pp. 231–242 (1989)
Kaplan, H., Rubin, N., Sharir, M.: Line transversal of convex polyhedra in \(\mathbb{R}^3\). SIAM J. Comput. 39(7), 3283–3310 (2010)
Lyons, K.A., Meijer, H., Rappaport, D.: Minimum polygon stabbers of isothetic line segments. Dept. of Computing and Information Science, Queen’s University, Canada (1990)
Mukhopadhyay, A., Kumar, C., Greene, E., Bhattacharya, B.: On intersecting a set of parallel line segments with a convex polygon of minimum area. Inf. Process. Lett. 105, 58–64 (2008)
Mukhopadhyay, A., Greene, E., Rao, S.V.: On intersecting a set of isothetic line segments with a convex polygon of minimum area. Int. J. Comput. Geom. Appl. 19(6), 557–577 (2009)
O’Rourke, J.: An on-line algorithm for fitting straight lines between data ranges. Commun. ACM 24, 574–578 (1981)
Pellegrini, M.: Lower bounds on stabbing lines in 3-space. Comput. Geom. Theory Appl. 3, 53–58 (1993)
Rappaport, D.: Minimum polygon transversals of line segments. Int. J. Comput. Geom. Appl. 5(3), 243–256 (1995)
Acknowledgments
M. C., C. S., and R.S were partially supported by projects MINECO MTM2012-30951 and Gen. Cat. DGR2014SGR46. D. G. was supported by project PAI FQM-0164. R.S. was partially funded by the Ramón y Cajal program (MINECO).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Claverol, M., Garijo, D., Korman, M., Seara, C., Silveira, R.I. (2015). Stabbing Segments with Rectilinear Objects. In: Kosowski, A., Walukiewicz, I. (eds) Fundamentals of Computation Theory. FCT 2015. Lecture Notes in Computer Science(), vol 9210. Springer, Cham. https://doi.org/10.1007/978-3-319-22177-9_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-22177-9_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-22176-2
Online ISBN: 978-3-319-22177-9
eBook Packages: Computer ScienceComputer Science (R0)