Skip to main content
2 of 4
Addendum, thanks, and a specific question isolated.
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

Random noncrossing chords of a circle

Suppose you generate random chords of a circle, with endpoints selected uniformly over the circumference, rejecting any chord that crosses a previously generated chord. The disk is then partitioned into regions bounded by chords alternating with circular arcs. For example, here are $n{=}100$ random noncrossing chords, with a region bounded by 5 chords highlighted (in green).
alt text http://cs.smith.edu/%7Eorourke/MathOverflow/Chords100.jpg
I am interested in the statistics of the structure of the dual trees for these regions. Assign each region a node, and connect two nodes by an edge if they share a chord. In the example above, the highlighted region's node has degree 5. Example questions: What is the expected maximum degree of a node for $n$ chords? Making a max-degree node the root, what is the expected height of the tree? (In the example above, the height is 21.) Etc.

Has anyone encountered this model before? Or a model sufficiently analogous to help establish these statistics? Thanks for any pointers!

Edit. Many thanks for the wealth of information provided by the community! I have not yet absorbed all the information in the cited papers, but so far I have not found this specific question answered (although it is likely implied, perhaps in the papers they cite): What is the expected maximum degree of a node as $n \rightarrow \infty$? What brought me to this topic in the first place is that I wondered if it might be near 3.

Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958