Complexities of efficient solutions of rectilinear polygon cover problems View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1997-04

AUTHORS

P. Berman, B. DasGupta

ABSTRACT

The rectilinear polygon cover problem is one in which a certain class of features of a rectilinear polygon ofn vertices has to be covered with the minimum number of rectangles included in the polygon. In particular, we consider covering the entire interior, the boundary, and the set of corners of the polygon. These problems have important applications in storing images and in the manufacture of integrated circuits. Unfortunately, most of these problems are known to be NP-complete. Hence it is necessary to develop efficient heuristics for these problems or to show that the design of efficient heuristics is impossible. In this paper we show:The corner cover problem is NP-complete.The boundary and the corner cover problem can be approximated within a ratio of 4 of the optimum inO(n logn) andO(n1.5) time, respectively.No polynomial-time approximation scheme exists for the interior and the boundary cover problems, unless P=NP. More... »

PAGES

331-356

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02523677

DOI

http://dx.doi.org/10.1007/bf02523677

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1023205821


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "P.", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Minnesota, 55455-0159, Minneapolis, MN, USA", 
          "id": "http://www.grid.ac/institutes/grid.17635.36", 
          "name": [
            "Department of Computer Science, University of Minnesota, 55455-0159, Minneapolis, MN, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "DasGupta", 
        "givenName": "B.", 
        "id": "sg:person.0763403270.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1997-04", 
    "datePublishedReg": "1997-04-01", 
    "description": "The rectilinear polygon cover problem is one in which a certain class of features of a rectilinear polygon ofn vertices has to be covered with the minimum number of rectangles included in the polygon. In particular, we consider covering the entire interior, the boundary, and the set of corners of the polygon. These problems have important applications in storing images and in the manufacture of integrated circuits. Unfortunately, most of these problems are known to be NP-complete. Hence it is necessary to develop efficient heuristics for these problems or to show that the design of efficient heuristics is impossible. In this paper we show:The corner cover problem is NP-complete.The boundary and the corner cover problem can be approximated within a ratio of 4 of the optimum inO(n logn) andO(n1.5) time, respectively.No polynomial-time approximation scheme exists for the interior and the boundary cover problems, unless P=NP.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf02523677", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "17"
      }
    ], 
    "keywords": [
      "cover problem", 
      "efficient heuristic", 
      "polynomial time approximation scheme", 
      "set of corners", 
      "efficient solution", 
      "heuristics", 
      "important applications", 
      "NPs", 
      "minimum number", 
      "approximation scheme", 
      "polygons", 
      "images", 
      "complexity", 
      "scheme", 
      "certain class", 
      "set", 
      "entire interior", 
      "rectangle", 
      "applications", 
      "vertices", 
      "features", 
      "design", 
      "solution", 
      "class", 
      "number", 
      "time", 
      "corner", 
      "circuit", 
      "manufacture", 
      "interior", 
      "ratio", 
      "problem", 
      "paper"
    ], 
    "name": "Complexities of efficient solutions of rectilinear polygon cover problems", 
    "pagination": "331-356", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1023205821"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02523677"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02523677", 
      "https://app.dimensions.ai/details/publication/pub.1023205821"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-05-20T07:20", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_297.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf02523677"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf02523677'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf02523677'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02523677'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02523677'


 

This table displays all metadata directly associated to this object as RDF triples.

101 TRIPLES      21 PREDICATES      59 URIs      51 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02523677 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N4bee1294f19f41268b5a53ed9086b673
4 schema:datePublished 1997-04
5 schema:datePublishedReg 1997-04-01
6 schema:description The rectilinear polygon cover problem is one in which a certain class of features of a rectilinear polygon ofn vertices has to be covered with the minimum number of rectangles included in the polygon. In particular, we consider covering the entire interior, the boundary, and the set of corners of the polygon. These problems have important applications in storing images and in the manufacture of integrated circuits. Unfortunately, most of these problems are known to be NP-complete. Hence it is necessary to develop efficient heuristics for these problems or to show that the design of efficient heuristics is impossible. In this paper we show:The corner cover problem is NP-complete.The boundary and the corner cover problem can be approximated within a ratio of 4 of the optimum inO(n logn) andO(n1.5) time, respectively.No polynomial-time approximation scheme exists for the interior and the boundary cover problems, unless P=NP.
7 schema:genre article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N59e5b75b35f54ae588079dcf8dbaa943
11 Nbbdce1b9e73f443ab50c9855244707bf
12 sg:journal.1047644
13 schema:keywords NPs
14 applications
15 approximation scheme
16 certain class
17 circuit
18 class
19 complexity
20 corner
21 cover problem
22 design
23 efficient heuristic
24 efficient solution
25 entire interior
26 features
27 heuristics
28 images
29 important applications
30 interior
31 manufacture
32 minimum number
33 number
34 paper
35 polygons
36 polynomial time approximation scheme
37 problem
38 ratio
39 rectangle
40 scheme
41 set
42 set of corners
43 solution
44 time
45 vertices
46 schema:name Complexities of efficient solutions of rectilinear polygon cover problems
47 schema:pagination 331-356
48 schema:productId N03461839c2a4461fb6583636bb556091
49 Nab88aa175c894e6fb711f61df048b31e
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023205821
51 https://doi.org/10.1007/bf02523677
52 schema:sdDatePublished 2022-05-20T07:20
53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
54 schema:sdPublisher N29766b614d4541a1a7361ada2071aaf6
55 schema:url https://doi.org/10.1007/bf02523677
56 sgo:license sg:explorer/license/
57 sgo:sdDataset articles
58 rdf:type schema:ScholarlyArticle
59 N03461839c2a4461fb6583636bb556091 schema:name dimensions_id
60 schema:value pub.1023205821
61 rdf:type schema:PropertyValue
62 N29766b614d4541a1a7361ada2071aaf6 schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 N4bee1294f19f41268b5a53ed9086b673 rdf:first sg:person.01274506210.27
65 rdf:rest N6c9ee866bf3c492cb610ded4d3562fbf
66 N59e5b75b35f54ae588079dcf8dbaa943 schema:issueNumber 4
67 rdf:type schema:PublicationIssue
68 N6c9ee866bf3c492cb610ded4d3562fbf rdf:first sg:person.0763403270.10
69 rdf:rest rdf:nil
70 Nab88aa175c894e6fb711f61df048b31e schema:name doi
71 schema:value 10.1007/bf02523677
72 rdf:type schema:PropertyValue
73 Nbbdce1b9e73f443ab50c9855244707bf schema:volumeNumber 17
74 rdf:type schema:PublicationVolume
75 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
76 schema:name Information and Computing Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
79 schema:name Computation Theory and Mathematics
80 rdf:type schema:DefinedTerm
81 sg:journal.1047644 schema:issn 0178-4617
82 1432-0541
83 schema:name Algorithmica
84 schema:publisher Springer Nature
85 rdf:type schema:Periodical
86 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
87 schema:familyName Berman
88 schema:givenName P.
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
90 rdf:type schema:Person
91 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.17635.36
92 schema:familyName DasGupta
93 schema:givenName B.
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
95 rdf:type schema:Person
96 grid-institutes:grid.17635.36 schema:alternateName Department of Computer Science, University of Minnesota, 55455-0159, Minneapolis, MN, USA
97 schema:name Department of Computer Science, University of Minnesota, 55455-0159, Minneapolis, MN, USA
98 rdf:type schema:Organization
99 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA
100 schema:name Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA
101 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...