Article

Free access

On piercing sets of objects

Authors:

Matthew J. Katz,

Franck NielsenAuthors Info & Claims

SCG '96: Proceedings of the twelfth annual symposium on Computational geometry

Pages 113 - 121

https://doi.org/10.1145/237218.237253

Published: 01 May 1996 Publication History

PDF eReader

References

[1]

N. Amenta. Helly-type theorems and generalized linear programming. Discrete Cornput. Geom., 12:241-261, 1994.

Digital Library

Google Scholar

[2]

M. Bellare, S. Goldwasser, C. Lund, and A. Russel. Efficient probabilistically checkable proofs and applications to approximation. In Proc. 25th A CM Symp. on Theory of Computing, pages 294-304, 1993.

Digital Library

Google Scholar

[3]

V. Chvatal. A greedy heuristic for the setcovering problem. Math. Oper. Res., 4:233- 235, 1979.

Digital Library

Google Scholar

[4]

B. Chazelle and J. Matou~ek. On lineartime deterministic algorithms for optimization problems in fixed dimension. In Proc. 4th A CM-$IAM $ymp. Discrete Algorithms, pages 281-290, 1993.

Digital Library

Google Scholar

[5]

L. Danzer and B. Griinbaum. Intersection properties of boxes in Rd. Combinatorica, 2(3):237-246, 1982.

Crossref

Google Scholar

[6]

L. Danzer, B. Griinbaum, and V. Klee. Helly's theorem and its relatives. In Proc. Syrup. Pure Math., pages 101-180, 1963.

Crossref

Google Scholar

[7]

R.J. Fowler, M. S. Paterson, and S. L. Tanimoto. Optimal packing and covering in the plane are NP-complete. Inform. Process. Left., 12(3):133-137, 1981.

Crossref

Google Scholar

[8]

P.M. Gruber and J. M. Wills, editors. Handbook of Convex Geometry, volume A. North-Holland, Amsterdam, the Netherlands, 1993.

Google Scholar

[9]

H. Hadwiger and H. Debrunner. Kombinatorische Geometric in der Ebene. Monographies de l'Enseignement Math~matique, N2, Geneva, 1960.

Google Scholar

[10]

D.S. Hochbaum. Approximation algorithms of the set covering and vertex cover problems. SIAM J. Computing, 11(3):555-556, 1982.

Crossref

Google Scholar

[11]

R. Karp. Reducibility among combinatorial problems, complexity of computer computations. E. Miller and J.W. Thatcher, New York, 1972.

Google Scholar

[12]

M. Katchalski and D. Nashtir. On a conjecture of Danzer and Griinbaum. In Proc. AMS, to appear.

Google Scholar

[13]

M.J. Katz and F. Nielsen. On piercing sets of objects. INRIA Technical Report, to appear.

Google Scholar

[14]

N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. J. A CM, 30:852-865, 1983.

Digital Library

Google Scholar

[15]

J. Matou~ek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. In Proc. 8th A CM Symp. on Computational Geometry, pages 1-8, 1992.

Digital Library

Google Scholar

[16]

M. Sharir. A near-linear algorithm for the planar 2-center problem. In Proc. 12th A CM Symp. on Computational Geometry, these proceedings.

Digital Library

Google Scholar

[17]

M. Sharir and E. Welzl. Rectilinear and polygonal p-piercing and p-center problems. In Proc. 12lh ACM $ymp. on Computational Geometry, these proceedings.

Digital Library

Google Scholar

Cited By

View all

Akram WSaxena S(2023)Point Enclosure Problem for Homothetic PolygonsCombinatorial Algorithms10.1007/978-3-031-34347-6_2(13-24)Online publication date: 3-Jun-2023
https://doi.org/10.1007/978-3-031-34347-6_2
Katz MKedem KSegal M(2006)Constrained square-center problemsAlgorithm Theory — SWAT'9810.1007/BFb0054358(95-106)Online publication date: 26-May-2006
https://doi.org/10.1007/BFb0054358
Segal M(2005)On piercing sets of axis-parallel rectangles and ringsAlgorithms — ESA '9710.1007/3-540-63397-9_33(430-442)Online publication date: 30-Jul-2005
https://doi.org/10.1007/3-540-63397-9_33
Show More Cited By

Index Terms

On piercing sets of objects
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
2. Theory of computation

Recommendations

Simple linear time algorithms for piercing pairwise intersecting disks
Abstract
A set D of disks in the plane is said to be pierced by a point set P if each disk in D contains a point of P. Any set of pairwise intersecting unit disks can be pierced by 3 points (Hadwiger and Debrunner (1955) [7]). Stachó and ...
Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line
COCOA 2015: Proceedings of the 9th International Conference on Combinatorial Optimization and Applications - Volume 9486

We consider special cases of [Figure not available: see fulltext.], [Figure not available: see fulltext.], [Figure not available: see fulltext.], and [Figure not available: see fulltext.] problems for axis-parallel squares and axis-parallel rectangles ...
Relationships between covering-based rough sets and relation-based rough sets

Rough set theory is an important technique to deal with vagueness and granularity in information systems. In rough set theory, relation-based rough sets and covering-based rough sets are two important extensions of the classical rough sets. This paper ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '96: Proceedings of the twelfth annual symposium on Computational geometry

May 1996

406 pages

ISBN:0897918045

DOI:10.1145/237218

Chairman:
Sue Whitesides
McGill Univ.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SoCG96

Sponsor:

SoCG96: 12th ACM Symposium on Computational Geometry

May 24 - 26, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

SCG '96 Paper Acceptance Rate 48 of 93 submissions, 52%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
362
Total Downloads

Downloads (Last 12 months)55
Downloads (Last 6 weeks)4

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Akram WSaxena S(2023)Point Enclosure Problem for Homothetic PolygonsCombinatorial Algorithms10.1007/978-3-031-34347-6_2(13-24)Online publication date: 3-Jun-2023
https://doi.org/10.1007/978-3-031-34347-6_2
Katz MKedem KSegal M(2006)Constrained square-center problemsAlgorithm Theory — SWAT'9810.1007/BFb0054358(95-106)Online publication date: 26-May-2006
https://doi.org/10.1007/BFb0054358
Segal M(2005)On piercing sets of axis-parallel rectangles and ringsAlgorithms — ESA '9710.1007/3-540-63397-9_33(430-442)Online publication date: 30-Jul-2005
https://doi.org/10.1007/3-540-63397-9_33
Nielsen F(2001)On point covers of c-oriented polygonsTheoretical Computer Science10.1016/S0304-3975(00)00227-9263:1-2(17-29)Online publication date: 28-Jul-2001
https://dl.acm.org/doi/10.1016/S0304-3975%2800%2900227-9
Agarwal PSen S(2001)Randomized Algorithms for Geometric Optimization ProblemsHandbook of Randomized Computing10.1007/978-1-4615-0013-1_6(151-202)Online publication date: 2001
https://doi.org/10.1007/978-1-4615-0013-1_6
Nielsen F(2000)Fast stabbing of boxes in high dimensionsTheoretical Computer Science10.1016/S0304-3975(98)00336-3246:1-2(53-75)Online publication date: 1-Sep-2000
https://dl.acm.org/doi/10.1016/S0304-3975%2898%2900336-3
Agarwal PSharir M(1998)Efficient algorithms for geometric optimizationACM Computing Surveys10.1145/299917.29991830:4(412-458)Online publication date: 1-Dec-1998
https://dl.acm.org/doi/10.1145/299917.299918
Nussbaum DChar BWang P(1997)Rectilinear p-piercing problemsProceedings of the 1997 international symposium on Symbolic and algebraic computation10.1145/258726.258828(316-323)Online publication date: 1-Jul-1997
https://dl.acm.org/doi/10.1145/258726.258828
Sharir MWelzl EWhitesides S(1996)Rectilinear and polygonal p-piercing and p-center problemsProceedings of the twelfth annual symposium on Computational geometry10.1145/237218.237255(122-132)Online publication date: 1-May-1996
https://dl.acm.org/doi/10.1145/237218.237255

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Simple linear time algorithms for piercing pairwise intersecting disks

Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line

Relationships between covering-based rough sets and relation-based rough sets