A PTAS for the horizontal rectangle stabbing problem Article Swipe

PDF

Arindam Khan , Aditya Subramanian , Andreas Wiese ·

YOU? · · 2021 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2111.05197

We study rectangle stabbing problems in which we are given $n$ axis-aligned rectangles in the plane that we want to stab, i.e., we want to select line segments such that for each given rectangle there is a line segment that intersects two opposite edges of it. In the horizontal rectangle stabbing problem (STABBING), the goal is to find a set of horizontal line segments of minimum total length such that all rectangles are stabbed. In general rectangle stabbing problem, also known as horizontal-vertical stabbing problem (HV-Stabbing), the goal is to find a set of rectilinear (i.e., either vertical or horizontal) line segments of minimum total length such that all rectangles are stabbed. Both variants are NP-hard. Chan, van Dijk, Fleszar, Spoerhase, and Wolff [2018]initiated the study of these problems by providing constant approximation algorithms. Recently, Eisenbrand, Gallato, Svensson, and Venzin [2021] have presented a QPTAS and a polynomial-time 8-approximation algorithm for STABBING but it is was open whether the problem admits a PTAS. In this paper, we obtain a PTAS for STABBING, settling this question. For HV-Stabbing, we obtain a $(2+\varepsilon)$-approximation. We also obtain PTASes for special cases of HV-Stabbing: (i) when all rectangles are squares, (ii) when each rectangle's width is at most its height, and (iii) when all rectangles are $δ$-large, i.e., have at least one edge whose length is at least $δ$, while all edge lengths are at most 1. Our result also implies improved approximations for other problems such as generalized minimum Manhattan network.

Related Topics

Concepts

Rectangle Combinatorics Line (geometry) Mathematics Line segment Approximation algorithm Plane (geometry) Geometry

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2111.05197
PDF: https://arxiv.org/pdf/2111.05197
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4226298009

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4226298009

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2111.05197

Digital Object Identifier
Title: A PTAS for the horizontal rectangle stabbing problem

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2021

Year of publication
Publication date: 2021-11-09

Full publication date if available
Authors: Arindam Khan, Aditya Subramanian, Andreas Wiese

List of authors in order
Landing page: https://arxiv.org/abs/2111.05197

Publisher landing page
PDF URL: https://arxiv.org/pdf/2111.05197

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2111.05197

Direct OA link when available
Concepts: Rectangle, Combinatorics, Line (geometry), Mathematics, Line segment, Approximation algorithm, Plane (geometry), Geometry

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4226298009
doi	https://doi.org/10.48550/arxiv.2111.05197
ids.doi	https://doi.org/10.48550/arxiv.2111.05197
ids.openalex	https://openalex.org/W4226298009
fwci
type	preprint
title	A PTAS for the horizontal rectangle stabbing problem
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T12420
topics[0].field.id	https://openalex.org/fields/25
topics[0].field.display_name	Materials Science
topics[0].score	0.869700014591217
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/2505
topics[0].subfield.display_name	Materials Chemistry
topics[0].display_name	Silicone and Siloxane Chemistry
topics[1].id	https://openalex.org/T11870
topics[1].field.id	https://openalex.org/fields/22
topics[1].field.display_name	Engineering
topics[1].score	0.8345000147819519
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2205
topics[1].subfield.display_name	Civil and Structural Engineering
topics[1].display_name	Structural Analysis and Optimization
topics[2].id	https://openalex.org/T10996
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.8108000159263611
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1704
topics[2].subfield.display_name	Computer Graphics and Computer-Aided Design
topics[2].display_name	Computational Geometry and Mesh Generation
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C2781302577
concepts[0].level	2
concepts[0].score	0.9612685441970825
concepts[0].wikidata	https://www.wikidata.org/wiki/Q209
concepts[0].display_name	Rectangle
concepts[1].id	https://openalex.org/C114614502
concepts[1].level	1
concepts[1].score	0.7145662307739258
concepts[1].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[1].display_name	Combinatorics
concepts[2].id	https://openalex.org/C198352243
concepts[2].level	2
concepts[2].score	0.5408786535263062
concepts[2].wikidata	https://www.wikidata.org/wiki/Q37105
concepts[2].display_name	Line (geometry)
concepts[3].id	https://openalex.org/C33923547
concepts[3].level	0
concepts[3].score	0.5208969116210938
concepts[3].wikidata	https://www.wikidata.org/wiki/Q395
concepts[3].display_name	Mathematics
concepts[4].id	https://openalex.org/C182124507
concepts[4].level	2
concepts[4].score	0.48994916677474976
concepts[4].wikidata	https://www.wikidata.org/wiki/Q166154
concepts[4].display_name	Line segment
concepts[5].id	https://openalex.org/C148764684
concepts[5].level	2
concepts[5].score	0.48820072412490845
concepts[5].wikidata	https://www.wikidata.org/wiki/Q621751
concepts[5].display_name	Approximation algorithm
concepts[6].id	https://openalex.org/C17825722
concepts[6].level	2
concepts[6].score	0.44905921816825867
concepts[6].wikidata	https://www.wikidata.org/wiki/Q17285
concepts[6].display_name	Plane (geometry)
concepts[7].id	https://openalex.org/C2524010
concepts[7].level	1
concepts[7].score	0.4008306860923767
concepts[7].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[7].display_name	Geometry
keywords[0].id	https://openalex.org/keywords/rectangle
keywords[0].score	0.9612685441970825
keywords[0].display_name	Rectangle
keywords[1].id	https://openalex.org/keywords/combinatorics
keywords[1].score	0.7145662307739258
keywords[1].display_name	Combinatorics
keywords[2].id	https://openalex.org/keywords/line
keywords[2].score	0.5408786535263062
keywords[2].display_name	Line (geometry)
keywords[3].id	https://openalex.org/keywords/mathematics
keywords[3].score	0.5208969116210938
keywords[3].display_name	Mathematics
keywords[4].id	https://openalex.org/keywords/line-segment
keywords[4].score	0.48994916677474976
keywords[4].display_name	Line segment
keywords[5].id	https://openalex.org/keywords/approximation-algorithm
keywords[5].score	0.48820072412490845
keywords[5].display_name	Approximation algorithm
keywords[6].id	https://openalex.org/keywords/plane
keywords[6].score	0.44905921816825867
keywords[6].display_name	Plane (geometry)
keywords[7].id	https://openalex.org/keywords/geometry
keywords[7].score	0.4008306860923767
keywords[7].display_name	Geometry
language	en
locations[0].id	pmh:oai:arXiv.org:2111.05197
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2111.05197
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2111.05197
locations[1].id	doi:10.48550/arxiv.2111.05197
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2111.05197
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5085907661
authorships[0].author.orcid	https://orcid.org/0000-0001-7505-1687
authorships[0].author.display_name	Arindam Khan
authorships[0].author_position	first
authorships[0].raw_author_name	Khan, Arindam
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5056872430
authorships[1].author.orcid	https://orcid.org/0000-0002-1398-1923
authorships[1].author.display_name	Aditya Subramanian
authorships[1].author_position	middle
authorships[1].raw_author_name	Subramanian, Aditya
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5067503013
authorships[2].author.orcid	https://orcid.org/0000-0003-3705-016X
authorships[2].author.display_name	Andreas Wiese
authorships[2].author_position	last
authorships[2].raw_author_name	Wiese, Andreas
authorships[2].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2111.05197
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	A PTAS for the horizontal rectangle stabbing problem
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T12420
primary_topic.field.id	https://openalex.org/fields/25
primary_topic.field.display_name	Materials Science
primary_topic.score	0.869700014591217
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/2505
primary_topic.subfield.display_name	Materials Chemistry
primary_topic.display_name	Silicone and Siloxane Chemistry
related_works	https://openalex.org/W2097569240, https://openalex.org/W4386442742, https://openalex.org/W2323975601, https://openalex.org/W2353000084, https://openalex.org/W2468848027, https://openalex.org/W4205730002, https://openalex.org/W2942906518, https://openalex.org/W1623138178, https://openalex.org/W2382326160, https://openalex.org/W2357946356
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2111.05197
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2111.05197
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2111.05197
primary_location.id	pmh:oai:arXiv.org:2111.05197
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2111.05197
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2111.05197
publication_date	2021-11-09
publication_year	2021
referenced_works_count	0
abstract_inverted_index.a	36, 58, 91, 143, 146, 161, 168, 179
abstract_inverted_index.1.	232
abstract_inverted_index.In	46, 74, 163
abstract_inverted_index.We	0, 181
abstract_inverted_index.as	81, 243
abstract_inverted_index.at	202, 215, 222, 230
abstract_inverted_index.by	129
abstract_inverted_index.in	5, 13
abstract_inverted_index.is	35, 55, 88, 154, 201, 221
abstract_inverted_index.it	153
abstract_inverted_index.of	44, 60, 64, 93, 102, 126, 188
abstract_inverted_index.or	98
abstract_inverted_index.to	19, 24, 56, 89
abstract_inverted_index.we	7, 17, 22, 166, 177
abstract_inverted_index.$n$	10
abstract_inverted_index.(i)	190
abstract_inverted_index.For	175
abstract_inverted_index.Our	233
abstract_inverted_index.all	70, 108, 192, 209, 226
abstract_inverted_index.and	121, 138, 145, 206
abstract_inverted_index.are	8, 72, 110, 114, 194, 211, 229
abstract_inverted_index.but	152
abstract_inverted_index.for	30, 150, 170, 185, 239
abstract_inverted_index.it.	45
abstract_inverted_index.its	204
abstract_inverted_index.one	217
abstract_inverted_index.set	59, 92
abstract_inverted_index.the	14, 47, 53, 86, 124, 158
abstract_inverted_index.two	41
abstract_inverted_index.van	117
abstract_inverted_index.was	155
abstract_inverted_index.(ii)	196
abstract_inverted_index.Both	112
abstract_inverted_index.PTAS	169
abstract_inverted_index.also	79, 182, 235
abstract_inverted_index.each	31, 198
abstract_inverted_index.edge	218, 227
abstract_inverted_index.find	57, 90
abstract_inverted_index.goal	54, 87
abstract_inverted_index.have	141, 214
abstract_inverted_index.line	26, 37, 62, 100
abstract_inverted_index.most	203, 231
abstract_inverted_index.open	156
abstract_inverted_index.such	28, 68, 106, 242
abstract_inverted_index.that	16, 29, 39, 69, 107
abstract_inverted_index.this	164, 173
abstract_inverted_index.want	18, 23
abstract_inverted_index.when	191, 197, 208
abstract_inverted_index.$δ$,	224
abstract_inverted_index.(iii)	207
abstract_inverted_index.Chan,	116
abstract_inverted_index.Dijk,	118
abstract_inverted_index.PTAS.	162
abstract_inverted_index.QPTAS	144
abstract_inverted_index.Wolff	122
abstract_inverted_index.cases	187
abstract_inverted_index.edges	43
abstract_inverted_index.given	9, 32
abstract_inverted_index.i.e.,	21, 213
abstract_inverted_index.known	80
abstract_inverted_index.least	216, 223
abstract_inverted_index.other	240
abstract_inverted_index.plane	15
abstract_inverted_index.stab,	20
abstract_inverted_index.study	1, 125
abstract_inverted_index.there	34
abstract_inverted_index.these	127
abstract_inverted_index.total	66, 104
abstract_inverted_index.which	6
abstract_inverted_index.while	225
abstract_inverted_index.whose	219
abstract_inverted_index.width	200
abstract_inverted_index.(i.e.,	95
abstract_inverted_index.PTASes	184
abstract_inverted_index.Venzin	139
abstract_inverted_index.[2021]	140
abstract_inverted_index.admits	160
abstract_inverted_index.either	96
abstract_inverted_index.length	67, 105, 220
abstract_inverted_index.obtain	167, 178, 183
abstract_inverted_index.paper,	165
abstract_inverted_index.result	234
abstract_inverted_index.select	25
abstract_inverted_index.general	75
abstract_inverted_index.height,	205
abstract_inverted_index.implies	236
abstract_inverted_index.lengths	228
abstract_inverted_index.minimum	65, 103, 245
abstract_inverted_index.problem	51, 84, 159
abstract_inverted_index.segment	38
abstract_inverted_index.special	186
abstract_inverted_index.whether	157
abstract_inverted_index.Fleszar,	119
abstract_inverted_index.Gallato,	136
abstract_inverted_index.NP-hard.	115
abstract_inverted_index.STABBING	151
abstract_inverted_index.constant	131
abstract_inverted_index.improved	237
abstract_inverted_index.network.	247
abstract_inverted_index.opposite	42
abstract_inverted_index.problem,	78
abstract_inverted_index.problems	4, 128, 241
abstract_inverted_index.segments	27, 63, 101
abstract_inverted_index.settling	172
abstract_inverted_index.squares,	195
abstract_inverted_index.stabbed.	73, 111
abstract_inverted_index.stabbing	3, 50, 77, 83
abstract_inverted_index.variants	113
abstract_inverted_index.vertical	97
abstract_inverted_index.Manhattan	246
abstract_inverted_index.Recently,	134
abstract_inverted_index.STABBING,	171
abstract_inverted_index.Svensson,	137
abstract_inverted_index.algorithm	149
abstract_inverted_index.presented	142
abstract_inverted_index.providing	130
abstract_inverted_index.question.	174
abstract_inverted_index.rectangle	2, 33, 49, 76
abstract_inverted_index.Spoerhase,	120
abstract_inverted_index.horizontal	48, 61
abstract_inverted_index.intersects	40
abstract_inverted_index.rectangles	12, 71, 109, 193, 210
abstract_inverted_index.$δ$-large,	212
abstract_inverted_index.(STABBING),	52
abstract_inverted_index.Eisenbrand,	135
abstract_inverted_index.algorithms.	133
abstract_inverted_index.generalized	244
abstract_inverted_index.horizontal)	99
abstract_inverted_index.rectangle's	199
abstract_inverted_index.rectilinear	94
abstract_inverted_index.HV-Stabbing,	176
abstract_inverted_index.HV-Stabbing:	189
abstract_inverted_index.axis-aligned	11
abstract_inverted_index.approximation	132
abstract_inverted_index.(HV-Stabbing),	85
abstract_inverted_index.approximations	238
abstract_inverted_index.8-approximation	148
abstract_inverted_index.[2018]initiated	123
abstract_inverted_index.polynomial-time	147
abstract_inverted_index.horizontal-vertical	82
abstract_inverted_index.$(2+\varepsilon)$-approximation.	180
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile