Recognizing convex polygons with few finger probes | Pattern Analysis and Applications
Skip to main content
Springer Nature Link
Log in

Recognizing convex polygons with few finger probes

  • Theoretical Advances
  • Published:
Pattern Analysis and Applications Aims and scope Submit manuscript

Abstract

The problem considered is that of recognizing if a given convex polygon belongs to a known collection by applying the so-called finger probes (i.e., probes by laser-like rays that each return the location of contact). Existing approaches use a number of probes that are linear in the number of sides of the polygon. The current premise is that probing is expensive, while computing is not. Accordingly, a method is proposed that recognizes a polygon (arbitrarily oriented) from the given collection, with high probability, using only a constant number of finger probes, at the cost of fairly large computing resources, particularly, in setting up and applying a range tree data structure. Analysis, though partly heuristic, is validated with software and experimental results.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Belleville P, Shermer TC (1993) Probing polygons minimally is hard. Comput Geom Theory Appl 2:255–265

    MATH  MathSciNet  Google Scholar 

  2. Bernstein HJ (1986) Determining the shape of a convex n-sided polygon using 2n + k tactile probes. Inf Process Lett 22:255–260

    Article  MATH  Google Scholar 

  3. CGAL, Computational geometry algorithms library. http://www.cgal.org

  4. Cole R, Yap CK (1987) Shape from probing. J Algorithms 8:19–38

    Article  MATH  MathSciNet  Google Scholar 

  5. de Berg M, van Kreveld M, Overmars M, Schwarzkopf O (2000) Computational geometry: algorithms and applications, 2nd edn. Springer, Heidelberg

    MATH  Google Scholar 

  6. Dobkin DP, Edelsbrunner H, Yap CK (1988) Probing convex polytopes. In: Proceedings of 18th ACM symposium on the theory of computing, pp 424–432

  7. Eves HW (1965) A survey of geometry, revised edn. Allyn and Bacon

  8. Freimer R, Khuller S, Mitchell JSB, Piatko C, Romanik K, Souvaine D (1995) Localizing an object with finger probes. In: Melter RA, Wu AY (eds) Proceedings of SPIE, vol 2356, vision geometry III, pp 272–283

  9. Joseph E, Skiena SS (1992) Model-based probing strategies for convex polygons. Comput Geom Theory Appl 2:209–221

    MATH  MathSciNet  Google Scholar 

  10. Levy SD: KDTree—A Java class for KD-tree search (exact and nearest-neighbor). http://www.cs.wlu.edu/∼levy

  11. PolyRecognition: polygon recognition software. http://www.cs.ait.ac.th/∼guha/papers/PolyRecognition.zip

  12. Romanik K (1995) Geometric probing and testing—a survey. DIMACS technical report 95-42

  13. Skiena SS (1998) Geometric probing. Ph.D. thesis, Department of Computer Science, University of Illinois at Urbana-Champaign

  14. Skiena SS (1992) Interactive reconstruction via geometric probing. Proc IEEE 80:1364–1383

    Article  Google Scholar 

Download references

Acknowledgments

We thank Chansophea Chuon and Nguyen Tan Khoa for help with the software. We thank the referees of this and the earlier conference version for several suggestions that helped improve the presentation significantly.

Author information

Authors and Affiliations

  1. Computer Science and Information Management Program, Asian Institute of Technology, P.O. Box 4, Klong Luang, Pathumthani, 12120, Thailand

    Sumanta Guha & Kiêu Trong Khánh

Authors
  1. Sumanta Guha
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kiêu Trong Khánh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sumanta Guha.

Additional information

Preliminary version appeared in Proceedings of the 11th International Conference on Computer Analysis of Images and Patterns (CAIP 2005), Versailles, France.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Guha, S., Khánh, K.T. Recognizing convex polygons with few finger probes. Pattern Anal Applic 12, 193–199 (2009). https://doi.org/10.1007/s10044-008-0117-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10044-008-0117-y

Keywords

Search

Navigation