Orthogonal segment stabbing

Matthew J. Katz; Joseph S.B. Mitchell; Yuval Nir

doi:10.1016/j.comgeo.2004.07.002

Orthogonal segment stabbing

Matthew J. Katz
, Joseph S.B. Mitchell
, Yuval Nir

Applied Mathematics and Statistics

Stony Brook University

Ben-Gurion University of the Negev

Research output: Contribution to journal › Article › peer-review

33 Scopus citations

Abstract

We study a class of geometric stabbing/covering problems for sets of line segments, rays and lines in the plane. While we demonstrate that the problems on sets of horizontal/vertical line segments are NP-complete, we show that versions involving (parallel) rays or lines are polynomially solvable.

Original language	English
Pages (from-to)	197-205
Number of pages	9
Journal	Computational Geometry: Theory and Applications
Volume	30
Issue number	2 SPEC. ISS.
DOIs	https://doi.org/10.1016/j.comgeo.2004.07.002
State	Published - Feb 2005

Keywords

Covering
Dynamic programming
Line segments
NP-completeness
Optimization
Rays
Stabbing

Access to Document

10.1016/j.comgeo.2004.07.002

Cite this

@article{f8ae8a617bd44c82865773f29195b719,

title = "Orthogonal segment stabbing",

abstract = "We study a class of geometric stabbing/covering problems for sets of line segments, rays and lines in the plane. While we demonstrate that the problems on sets of horizontal/vertical line segments are NP-complete, we show that versions involving (parallel) rays or lines are polynomially solvable.",

keywords = "Covering, Dynamic programming, Line segments, NP-completeness, Optimization, Rays, Stabbing",

author = "Katz, \{Matthew J.\} and Mitchell, \{Joseph S.B.\} and Yuval Nir",

year = "2005",

month = feb,

doi = "10.1016/j.comgeo.2004.07.002",

language = "English",

volume = "30",

pages = "197--205",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "2 SPEC. ISS.",

}

TY - JOUR

T1 - Orthogonal segment stabbing

AU - Katz, Matthew J.

AU - Mitchell, Joseph S.B.

AU - Nir, Yuval

PY - 2005/2

Y1 - 2005/2

N2 - We study a class of geometric stabbing/covering problems for sets of line segments, rays and lines in the plane. While we demonstrate that the problems on sets of horizontal/vertical line segments are NP-complete, we show that versions involving (parallel) rays or lines are polynomially solvable.

AB - We study a class of geometric stabbing/covering problems for sets of line segments, rays and lines in the plane. While we demonstrate that the problems on sets of horizontal/vertical line segments are NP-complete, we show that versions involving (parallel) rays or lines are polynomially solvable.

KW - Covering

KW - Dynamic programming

KW - Line segments

KW - NP-completeness

KW - Optimization

KW - Rays

KW - Stabbing

UR - https://www.scopus.com/pages/publications/10044269609

U2 - 10.1016/j.comgeo.2004.07.002

DO - 10.1016/j.comgeo.2004.07.002

M3 - Article

SN - 0925-7721

VL - 30

SP - 197

EP - 205

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 2 SPEC. ISS.

ER -

Orthogonal segment stabbing

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this