More Web Proxy on the site http://driver.im/

article

Geometric knapsack problems

Authors:

Esther M. Arkin,

Joseph S. MitchellAuthors Info & Claims

Algorithmica, Volume 10, Issue 5

Pages 399 - 427

https://doi.org/10.1007/BF01769706

Published: 01 November 1993 Publication History

Abstract

We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following "fence enclosure" problem: given a setS ofn points in the plane with valuesvi ź 0, we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the "value" of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, such as allowingS to consist of points and/or simple polygons. Other versions of the problems are obtained by restricting the total amount of fence available and also allowing the enclosure to consist of at mostM connected components. When there is an upper bound on the length of fence available, we show that the problem is NP-complete. We also provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.

References

[1]

A. Aggarwal, M. Klawe, S. Moran, P. Shor, and R. Wilber, Geometric applications of a matrix searching algorithm, Algorithmica, 2 (1987), 195-208.

Digital Library

[2]

M. Atallah, R. Cole, and M. T. Goodrich, Cascading divide-and-conquer, SIAM Journal on Computing, 18 (1989), 499-532.

Digital Library

[3]

D. Bienstock and C. L. Monma, Optimal enclosing regions in planar graphs, Networks, 19 (1989), 79-94.

[4]

J. E. Boyce, D. P. Dobkin, R. L. Drysdale, and L. J. Guibas, Finding extremal polygons, SIAM Journal on Computing, 14 (1985), 134-147.

Digital Library

[5]

V. Capoyleas, G. Rote, and G. Woeginger, Geometric clusterings, Journal of Algorithms, 12 (1991), 341-356.

Digital Library

[6]

J. S. Chang, Polygon Optimization Problems, Ph.D. Dissertation, Technical Report No. 240, Robotics Report No. 78, Department of Computer Science, New York University, August, 1986.

[7]

J. S. Chang and C. K. Yap, A polynomial solution for the potato peeling problem, Discrete and Computational Geometry, 1 (1986), 155-182.

Digital Library

[8]

B. Chazelle, The polygon containment problem, Advances in Computing Research, JAI Press, Greenwich, CT, 1983, pp. 1-33.

[9]

V. Chvatal, Linear Programming, Freeman, San Francisco, CA, 1983, pp. 374-380.

[10]

G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.

[11]

P. Eades and D. Rappaport, The complexity of computing minimum separating polygons, Pattern Recognition Letters (1993), to appear.

[12]

H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987.

[13]

H. Edelsbrunner, A. D. Robinson, and X. Shen, Covering Convex Sets with Non-Overlapping Polygons, Discrete Mathematics, 81 (1990), 153-164.

Digital Library

[14]

D. Eppstein, M. Overmars, G. Rote, and G. Woeginger, Finding minimum area k-gons, Discrete and Computational Geometry, 7 (1992), 45-58.

Digital Library

[15]

L. Fejes Toth, Some packing and covering theorems, Acta Universitatis Szegediensis. Acta Scientiarum Mathematicarum, A 12 (1950), 62-67.

[16]

M. Fredman and R. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, 34 (1987), 596-615.

Digital Library

[17]

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1978.

Digital Library

[18]

R. S. Garfinkel and G. L. Nemhauser, Integer Programming, Wiley, New York, 1972.

[19]

S. K. Ghosh and D. M. Mount, An output sensitive algorithm for computing visibility graphs, SIAM Journal on Computing, 20 (1991), 888-910.

Digital Library

[20]

D. S. Hochbaum and W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM, 32 (1985), 130-136.

Digital Library

[21]

J. JáJá, An Introduction to Parallel Algorithms, Addison-Wesley, Reading, MA, 1991.

[22]

B. Korte and L. Lovasz, Polyhedral results on antimatroids, Proceedings of the New York Combinatorics Conference, to appear.

[23]

D. T. Lee and Y. T. Ching, The power of geometric duality revisited, Information Processing Letters, 21 (1985), 117-122.

[24]

S. Martello and P. Toth, Knapsack Problems--Algorithms and Computer Implementations, Wiley, New York, 1990.

[25]

D. Mount and R. Silverman, Packing and covering the plane with translates of a convex polygon, Journal of Algorithms, 11 (1990), 564-580.

Digital Library

[26]

C. H. Papadimitrious and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, NJ, 1982.

Cited By

Segal-Halevi E(2022)Redividing the cakeAutonomous Agents and Multi-Agent Systems10.1007/s10458-022-09545-x36:1Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s10458-022-09545-x
Pilz AWelzl EWettstein M(2020)From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few VerticesDiscrete & Computational Geometry10.1007/s00454-019-00147-164:3(1067-1097)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1007/s00454-019-00147-1
Abrahamsen Mde Berg MBuchin KMehr MMehrabi A(2020)Minimum Perimeter-Sum Partitions in the PlaneDiscrete & Computational Geometry10.1007/s00454-019-00059-063:2(483-505)Online publication date: 1-Mar-2020
https://dl.acm.org/doi/10.1007/s00454-019-00059-0
Show More Cited By

Geometric knapsack problems

Recommendations

Widest-corridor problems

A k-dense corridor through a finite set, S, of n points in the plane is the open region of the plane that is bounded by two parallel lines that intersect the convex hull of S and such that the region contains k points of S. The problem of finding a ...
Geometric separability using orthogonal objects
Highlights
- An efficient algorithm for bichromatic separability for rectangular and square annuli.
Abstract
Given a bichromatic point set P = R ∪ B of red and blue points, a separator is an object of a certain type that separates R and B. We study the geometric separability problem when the separator is a) rectangular annulus of fixed ...
Algorithms for Reporting and Counting Geometric Intersections

An interesting class of "geometric intersection problems" calls for dealing with the pairwise intersections among a set of N objects in the plane, These problems arise in many applications such as printed circuit design, architectural data bases, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 10, Issue 5

November 1993

75 pages

ISSN:0178-4617

Issue’s Table of Contents

Copyright © Copyright © 1993 Springer-Verlag New York Inc.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 November 1993

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Segal-Halevi E(2022)Redividing the cakeAutonomous Agents and Multi-Agent Systems10.1007/s10458-022-09545-x36:1Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s10458-022-09545-x
Pilz AWelzl EWettstein M(2020)From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few VerticesDiscrete & Computational Geometry10.1007/s00454-019-00147-164:3(1067-1097)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1007/s00454-019-00147-1
Abrahamsen Mde Berg MBuchin KMehr MMehrabi A(2020)Minimum Perimeter-Sum Partitions in the PlaneDiscrete & Computational Geometry10.1007/s00454-019-00059-063:2(483-505)Online publication date: 1-Mar-2020
https://dl.acm.org/doi/10.1007/s00454-019-00059-0
Abrahamsen MAdamaszek ABringmann KCohen-Addad VMehr MRotenberg ERoytman AThorup MDiakonikolas IKempe DHenzinger M(2018)Fast fencingProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188878(564-573)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188878
Bereg SDíaz-Báñez JFlores-Peñaloza DLangerman SPérez-Lantero PUrrutia J(2016)Optimizing some constructions with barsJournal of Combinatorial Optimization10.1007/s10878-014-9816-z31:3(1160-1173)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1007/s10878-014-9816-z
Alt HArkin EEfrat AHart GHurtado FKostitsyna IKröller AMitchell JPolishchuk V(2014)Scandinavian Thins on Top of CakeTheory of Computing Systems10.1007/s00224-013-9493-954:4(689-714)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1007/s00224-013-9493-9
Aronov BKreveld MLöffler MSilveira R(2011)Peeling Meshed PotatoesAlgorithmica10.5555/3118782.311922260:2(349-367)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.5555/3118782.3119222
Reinbacher IBenkert MKreveld MMitchell JSnoeyink JWolff A(2008)Delineating Boundaries for Imprecise RegionsAlgorithmica10.5555/3118752.311897550:3(386-414)Online publication date: 1-Mar-2008
https://dl.acm.org/doi/10.5555/3118752.3118975
Chambers Ede Verdière ÉErickson JLazarus FWhittlesey KAmenta NCheong O(2006)Splitting (complicated) surfaces is hardProceedings of the twenty-second annual symposium on Computational geometry10.1145/1137856.1137918(421-429)Online publication date: 5-Jun-2006
https://dl.acm.org/doi/10.1145/1137856.1137918
Gudmundsson JLevcopoulos C(1999)A fast approximation algorithm for TSP with neighborhoodsNordic Journal of Computing10.5555/642160.6421676:4(469-488)Online publication date: 1-Dec-1999
https://dl.acm.org/doi/10.5555/642160.642167
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents