Two Geometric Optimization Problems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1994

AUTHORS

Bhaskar Dasgupta , Vwani Roychowdhury

ABSTRACT

We consider two optimization problems with geometric structures. The first one concerns the foUowing minimization problem, termed as the rectilinear polygon cover problem: “Cover certain features of a given rectilinear polygon (possibly with rectilinear holes) with the minimum number of rectangles included in the polygon.” Depending upon whether one wants to cover the interior, boundary or corners of the polygon, the problem is termed as the interior, boundary or corner cover problem, respectively. Most of these problems are known to be NP-complete. In this chapter we survey some of the important previous results for these problems find provide a proof of impossibility of a polynomial-time approximation scheme for the interior and boundary cover problems. The second problem concerns routing in a segmented routing channel. The related problems are fundamental to routing and design automation for Field Programmable Gate Arrays (FPGAs), a new type of electrically programmable VLSI. In this chapter we survey the theoretical results on the combinatorial complexity and algorithm design for segmented channel routing. It is known that the segmented channel routing problem is in general NP-Complete. Efficient polynomial time algorithms for a number of important special cases are presented. More... »

PAGES

30-57

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-1-4613-3629-7_3

DOI

http://dx.doi.org/10.1007/978-1-4613-3629-7_3

DIMENSIONS

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


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, 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": "Bhaskar", 
        "id": "sg:person.0763403270.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Electrical Engineering, Purdue University, 47907-1285, West Lafayette, IN, USA", 
          "id": "http://www.grid.ac/institutes/grid.169077.e", 
          "name": [
            "School of Electrical Engineering, Purdue University, 47907-1285, West Lafayette, IN, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Roychowdhury", 
        "givenName": "Vwani", 
        "id": "sg:person.01342527761.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01342527761.33"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1994", 
    "datePublishedReg": "1994-01-01", 
    "description": "We consider two optimization problems with geometric structures. The first one concerns the foUowing minimization problem, termed as the rectilinear polygon cover problem: \u201cCover certain features of a given rectilinear polygon (possibly with rectilinear holes) with the minimum number of rectangles included in the polygon.\u201d Depending upon whether one wants to cover the interior, boundary or corners of the polygon, the problem is termed as the interior, boundary or corner cover problem, respectively. Most of these problems are known to be NP-complete. In this chapter we survey some of the important previous results for these problems find provide a proof of impossibility of a polynomial-time approximation scheme for the interior and boundary cover problems. The second problem concerns routing in a segmented routing channel. The related problems are fundamental to routing and design automation for Field Programmable Gate Arrays (FPGAs), a new type of electrically programmable VLSI. In this chapter we survey the theoretical results on the combinatorial complexity and algorithm design for segmented channel routing. It is known that the segmented channel routing problem is in general NP-Complete. Efficient polynomial time algorithms for a number of important special cases are presented.", 
    "editor": [
      {
        "familyName": "Du", 
        "givenName": "Ding-Zhu", 
        "type": "Person"
      }, 
      {
        "familyName": "Sun", 
        "givenName": "Jie", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-1-4613-3629-7_3", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-1-4613-3631-0", 
        "978-1-4613-3629-7"
      ], 
      "name": "Advances in Optimization and Approximation", 
      "type": "Book"
    }, 
    "keywords": [
      "optimization problem", 
      "cover problem", 
      "geometric optimization problems", 
      "polynomial time approximation scheme", 
      "efficient polynomial time algorithm", 
      "important special case", 
      "Field Programmable Gate Array", 
      "important previous results", 
      "approximation scheme", 
      "general NP-Complete", 
      "polynomial time algorithm", 
      "minimization problem", 
      "theoretical results", 
      "proof of impossibility", 
      "geometric structure", 
      "combinatorial complexity", 
      "special case", 
      "time algorithm", 
      "second problem", 
      "rectilinear polygons", 
      "minimum number", 
      "related problems", 
      "programmable gate array", 
      "algorithm design", 
      "NP-Complete", 
      "routing channels", 
      "problem", 
      "previous results", 
      "first one", 
      "gate array", 
      "polygons", 
      "design automation", 
      "segmented channel routing", 
      "certain features", 
      "routing", 
      "segmented channel", 
      "scheme", 
      "algorithm", 
      "channel routing", 
      "programmable VLSI", 
      "rectangle", 
      "proof", 
      "new type", 
      "one", 
      "complexity", 
      "number", 
      "NPs", 
      "channels", 
      "results", 
      "VLSI", 
      "array", 
      "corner", 
      "structure", 
      "impossibility", 
      "design", 
      "chapter", 
      "cases", 
      "features", 
      "automation", 
      "types"
    ], 
    "name": "Two Geometric Optimization Problems", 
    "pagination": "30-57", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1032748234"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-1-4613-3629-7_3"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-1-4613-3629-7_3", 
      "https://app.dimensions.ai/details/publication/pub.1032748234"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:46", 
    "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/chapter/chapter_352.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-1-4613-3629-7_3"
  }
]
 

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/978-1-4613-3629-7_3'

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/978-1-4613-3629-7_3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-3629-7_3'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-3629-7_3'


 

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

135 TRIPLES      23 PREDICATES      85 URIs      78 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-1-4613-3629-7_3 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N3f0787e1a37d4887b5928080b9b11c1e
4 schema:datePublished 1994
5 schema:datePublishedReg 1994-01-01
6 schema:description We consider two optimization problems with geometric structures. The first one concerns the foUowing minimization problem, termed as the rectilinear polygon cover problem: “Cover certain features of a given rectilinear polygon (possibly with rectilinear holes) with the minimum number of rectangles included in the polygon.” Depending upon whether one wants to cover the interior, boundary or corners of the polygon, the problem is termed as the interior, boundary or corner cover problem, respectively. Most of these problems are known to be NP-complete. In this chapter we survey some of the important previous results for these problems find provide a proof of impossibility of a polynomial-time approximation scheme for the interior and boundary cover problems. The second problem concerns routing in a segmented routing channel. The related problems are fundamental to routing and design automation for Field Programmable Gate Arrays (FPGAs), a new type of electrically programmable VLSI. In this chapter we survey the theoretical results on the combinatorial complexity and algorithm design for segmented channel routing. It is known that the segmented channel routing problem is in general NP-Complete. Efficient polynomial time algorithms for a number of important special cases are presented.
7 schema:editor Nab1e298f26b24968a03e6b82f3ae11dd
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N381083b3bbaf4556b37e795794ce3920
12 schema:keywords Field Programmable Gate Array
13 NP-Complete
14 NPs
15 VLSI
16 algorithm
17 algorithm design
18 approximation scheme
19 array
20 automation
21 cases
22 certain features
23 channel routing
24 channels
25 chapter
26 combinatorial complexity
27 complexity
28 corner
29 cover problem
30 design
31 design automation
32 efficient polynomial time algorithm
33 features
34 first one
35 gate array
36 general NP-Complete
37 geometric optimization problems
38 geometric structure
39 important previous results
40 important special case
41 impossibility
42 minimization problem
43 minimum number
44 new type
45 number
46 one
47 optimization problem
48 polygons
49 polynomial time algorithm
50 polynomial time approximation scheme
51 previous results
52 problem
53 programmable VLSI
54 programmable gate array
55 proof
56 proof of impossibility
57 rectangle
58 rectilinear polygons
59 related problems
60 results
61 routing
62 routing channels
63 scheme
64 second problem
65 segmented channel
66 segmented channel routing
67 special case
68 structure
69 theoretical results
70 time algorithm
71 types
72 schema:name Two Geometric Optimization Problems
73 schema:pagination 30-57
74 schema:productId Na839198712674715b9d6e78cb5aa6ed9
75 Ne9e0a430c123402f8b50136b15819c45
76 schema:publisher N30793df1371744289f2ecc521e41ae00
77 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032748234
78 https://doi.org/10.1007/978-1-4613-3629-7_3
79 schema:sdDatePublished 2022-05-20T07:46
80 schema:sdLicense https://scigraph.springernature.com/explorer/license/
81 schema:sdPublisher N603346bfd6fc4d428c25a7b0de1ac1b1
82 schema:url https://doi.org/10.1007/978-1-4613-3629-7_3
83 sgo:license sg:explorer/license/
84 sgo:sdDataset chapters
85 rdf:type schema:Chapter
86 N00fd985b13d54608b71d208512b4605e schema:familyName Sun
87 schema:givenName Jie
88 rdf:type schema:Person
89 N30793df1371744289f2ecc521e41ae00 schema:name Springer Nature
90 rdf:type schema:Organisation
91 N381083b3bbaf4556b37e795794ce3920 schema:isbn 978-1-4613-3629-7
92 978-1-4613-3631-0
93 schema:name Advances in Optimization and Approximation
94 rdf:type schema:Book
95 N3f0787e1a37d4887b5928080b9b11c1e rdf:first sg:person.0763403270.10
96 rdf:rest N9dbd7cfe73e2417eb96c8d685d5680b0
97 N603346bfd6fc4d428c25a7b0de1ac1b1 schema:name Springer Nature - SN SciGraph project
98 rdf:type schema:Organization
99 N9ad73461bd134effb34c0e709582c950 rdf:first N00fd985b13d54608b71d208512b4605e
100 rdf:rest rdf:nil
101 N9dbd7cfe73e2417eb96c8d685d5680b0 rdf:first sg:person.01342527761.33
102 rdf:rest rdf:nil
103 N9f7d4a5f996340d7bbd90941e194b0bc schema:familyName Du
104 schema:givenName Ding-Zhu
105 rdf:type schema:Person
106 Na839198712674715b9d6e78cb5aa6ed9 schema:name doi
107 schema:value 10.1007/978-1-4613-3629-7_3
108 rdf:type schema:PropertyValue
109 Nab1e298f26b24968a03e6b82f3ae11dd rdf:first N9f7d4a5f996340d7bbd90941e194b0bc
110 rdf:rest N9ad73461bd134effb34c0e709582c950
111 Ne9e0a430c123402f8b50136b15819c45 schema:name dimensions_id
112 schema:value pub.1032748234
113 rdf:type schema:PropertyValue
114 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
115 schema:name Information and Computing Sciences
116 rdf:type schema:DefinedTerm
117 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
118 schema:name Computation Theory and Mathematics
119 rdf:type schema:DefinedTerm
120 sg:person.01342527761.33 schema:affiliation grid-institutes:grid.169077.e
121 schema:familyName Roychowdhury
122 schema:givenName Vwani
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01342527761.33
124 rdf:type schema:Person
125 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.17635.36
126 schema:familyName Dasgupta
127 schema:givenName Bhaskar
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
129 rdf:type schema:Person
130 grid-institutes:grid.169077.e schema:alternateName School of Electrical Engineering, Purdue University, 47907-1285, West Lafayette, IN, USA
131 schema:name School of Electrical Engineering, Purdue University, 47907-1285, West Lafayette, IN, USA
132 rdf:type schema:Organization
133 grid-institutes:grid.17635.36 schema:alternateName Department of Computer Science, University of Minnesota, 55455-0159, Minneapolis, MN, USA
134 schema:name Department of Computer Science, University of Minnesota, 55455-0159, Minneapolis, MN, USA
135 rdf:type schema:Organization
 




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


...