Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Right angle free subsets in the plane

  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

In this paper we investigate the complexity of finding maximum right angle free subsets of a given set of points in the plane. For a set of rational pointsP in the plane, theright angle number ρ(P) (respectivelyrectilinear right angle number ρ R (P)) ofP is the cardinality of a maximum subset ofP, no three members of which form a right angle triangle (respectively a right angle triangle with its side or base parallel to thex-axis). It is shown that both parameters areNP-hard to compute. The latter problem is also shown to be equivalent to finding a minimum dominating set in a bipartite graph. This is used to show that there is a polynomial algorithm for computingρ R (P) whenP is a horizontally-convex subset of the lattice ℤ × ℤ (P ishorizontally-convex if for any pair of points inP which lie on a horizontal line, every lattice point between them is also inP). We then show that this algorithm yields a 1/2-approximate algorithm for the right angle number of a convex subregion of the lattice.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abbott, H.L.: On a Conjecture of Erdös and Silverman in Combinatorial Geometry. J. Comb. Theory, Ser. A29, 380–381 (1980)

    Google Scholar 

  2. Bertossi, A.A.: Dominating sets for split and bipartite graphs, unpublished manuscript (1982)

  3. Chang, G.J., Nemhauser, G.L.: “Thek-domination andk-stability problem of graphs”, Report No. 540, School of OR&IE, Cornell University, Ithaca, N.Y. (1982)

    Google Scholar 

  4. Damaschke, P., Müller, H., Kratsch, D.: Domination in convex and chordal bipartite graphs. Inf. Process. Lett.36, 231–236 (1990)

    Article  Google Scholar 

  5. Erdös, P.: Problems and Results in Combinatorial Analysis; Proceedings, Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium XIX (F. Hoffman et al. Eds.) 3–12, (1977)

  6. Lemke, Paul: A Counterexample to a Conjecture of Abbott. J. Comb. Theory, Ser. A50, 301–304 (1989)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Kellogg School of Management, Northwestern University, Chicago, IL, USA

    B. Gamble

  2. T.J. Watson Research Center, IBM, Yorktown Heights, NY, USA

    W. Pulleyblank

  3. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada

    B. Reed

  4. Centre for Mathematics and Computer Science, P.O. Box 4079, 1009AB, Amsterdam, The Netherlands

    B. Shepherd

Authors
  1. B. Gamble
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. W. Pulleyblank
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. B. Reed
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. B. Shepherd
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gamble, B., Pulleyblank, W., Reed, B. et al. Right angle free subsets in the plane. Graphs and Combinatorics 11, 121–129 (1995). https://doi.org/10.1007/BF01929481

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01929481

Keywords

Search

Navigation