Interactions between Digital Geometry and Combinatorics on Words

Details Interactions between Digital Geometry and Combinatorics on Words Interactions between Digital Geometry and Combinatorics on Words

2011-08-18

arxiv.org/abs/1108.3615v1

EPTCS 63, 2011, pp. 1-12

Computer Science

Computational Geometry

In Proceedings WORDS 2011, arXiv:1108.3412

Scientific paper

10.4204/EPTCS.63.1

We review some recent results in digital geometry obtained by using a combinatorics on words approach to discrete geometry. Motivated on the one hand by the well-known theory of Sturmian words which model conveniently discrete lines in the plane, and on the other hand by the development of digital geometry, this study reveals strong links between the two fields. Discrete figures are identified with polyominoes encoded by words. The combinatorial tools lead to elegant descriptions of geometrical features and efficient algorithms. Among these, radix-trees are useful for efficiently detecting path intersection, Lyndon and Christoffel words appear as the main tools for describing digital convexity; equations on words allow to better understand tilings by translations.

Affiliated with

Also associated with

No associations

Rating

Interactions between Digital Geometry and Combinatorics on Words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Interactions between Digital Geometry and Combinatorics on Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interactions between Digital Geometry and Combinatorics on Words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-180551