Module: DataStructuresRMolinari::Algorithms

Includes:
Shared
Defined in:
lib/data_structures_rmolinari/algorithms.rb

Overview

Algorithms that use the module’s data structures but don’t belong as a method on one of the data structures

Constant Summary

Constants included from Shared

Shared::INFINITY

Class Method Summary collapse

Methods included from Shared

#contains_duplicates?

Class Method Details

.first_k(enumerable, k, &block) ⇒ Object

Given an enumerable and a number k, return the k smallest items from the enumerable in ascending order.

If a block is given, each element is yielded to the block to determin its sort key. Otherwise each element is its own sort key.

We use a heap of size k. Run time is O(n log k).

TODO: offer to return the best k items unsorted, which will be slightly faster. This requires changing Heap to produce the contents all at once. Probably not worth the trouble.



108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/data_structures_rmolinari/algorithms.rb', line 108

def self.first_k(enumerable, k, &block)
  heap = DataStructuresRMolinari::Heap.new(max_heap: true, addressable: false)

  enumerable.each do |item|
    priority = if block_given?
      yield item
    else
      item
    end

    if heap.size < k
      heap.insert(item, priority)
    elsif priority < heap.top_priority
      heap.pop
      heap.insert(item, priority)
    end
  end

  result = []
  result << heap.pop until heap.empty?
  result.reverse
end

.maximal_empty_rectangles(points) ⇒ Object

We are given a set P of points in the x-y plane. An _empty rectangle for P_ is a rectangle (left, right, bottom, top) satisifying the following

- it has positive area;
- its sides are parallel to the axes;
- it lies within the smallest bounding box (x_min, x_max, y_min, y_max) containing P; and
- no point of P lies in its interior.

A _maximal empty rectangle_ (MER) for P is an empty rectangle for P not properly contained in any other.

We enumerate all maximal empty rectangles for P, yielding each as (left, right, bottom, top). The algorithm is due to De, M., Maheshwari, A., Nandy, S. C., Smid, M., _An In-Place Min-max Priority Search Tree_, Computational Geometry, v46 (2013), pp 310-327.

It runs in O(m log n) time, where m is the number of MERs enumerated and n is the number of points in P. (Constructing the MaxPST takes O(n log^2 n) time, but m = O(n^2) so we are still O(m log n) overall.)

Parameters:

  • points (Array) —

    an array of points in the x-y plane. Each must respond to x and y.



22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
# File 'lib/data_structures_rmolinari/algorithms.rb', line 22

def self.maximal_empty_rectangles(points)
  # We break the emtpy rectangles into three types
  #   1. bounded at bottom and top by y_min and y_max
  #   2. bounded at the top by y_max and at the bottom by one of the points of P
  #   3. bounded at the top by a point in P

  return if points.size <= 1

  sorted_points = points.sort_by(&:x)
  x_min = sorted_points.first.x
  x_max = sorted_points.last.x

  # This is O(n).  But it also O(m) beacause consecutive pairs of points produce a type 1 rectangle.
  y_min, y_max = sorted_points.map(&:y).minmax

  # Enumerate type 1
  sorted_points.each_cons(2) do |pt1, pt2|
    next if pt1.x == pt2.x

    yield [pt1.x, pt2.x, y_min, y_max]
  end

  # This builds its internal structure inside sorted_points itself.
  max_pst = DataStructuresRMolinari::MaxPrioritySearchTree.new(sorted_points, dynamic: true)

  # Enumerate type 2. We consider each point of P and work out the largest rectangle bounded below by P and above by y_max. The
  # points constraining us on the left and right are given by queries on the MaxPST.
  points.each do |pt|
    next if pt.y == y_max # 0 area
    next if pt.y == y_min # type 1

    # Open region means we don't just get pt back again. The De et al. paper is rather vague.
    left_bound  = max_pst.largest_x_in_nw(pt.x, pt.y, open: true)
    right_bound = max_pst.smallest_x_in_ne(pt.x, pt.y, open: true)

    left = left_bound.x.infinite? ? x_min : left_bound.x
    right = right_bound.x.infinite? ? x_max : right_bound.x
    next if left == right

    yield [left, right, pt.y, y_max]
  end

  # Enumerate type 3. This is the cleverest part of the algorithm. Start with a point (x0, y0) in P. We imagine a horizontal line
  # drawing down over the bounding rectangle, starting at y = y0 with l = x_min and r = x_max. Every time we meet another point
  # (x1, y1) of P we emit a maximal rectangle and shorten the horizonal line. At any time, the next point that we encounter is the
  # highest (max y) point in the region l < x < r and y >= y_min.
  #
  # If we have a MaxPST containing with the points (x0, y0) and above deleted, (x1, y1) is almost given by
  #
  #      largest_y_in_3_sided(l, r, y_min)
  #
  # That call considers the points in the closed region l <= x <= r and y >= y_min, so we use an open search region instead.
  until max_pst.empty?
    top_pt = max_pst.delete_top!
    top = top_pt.y
    next if top == y_max # this one is type 1 or 2
    next if top == y_min # zero area: no good

    l = x_min
    r = x_max

    loop do
      next_pt = max_pst.largest_y_in_3_sided(l, r, y_min, open: true)

      bottom = next_pt.y.infinite? ? y_min : next_pt.y
      yield [l, r, bottom, top]

      break if next_pt.y.infinite? # we have reached the bottom

      if next_pt.x < top_pt.x
        l = next_pt.x
      else
        r = next_pt.x
      end
    end
  end
end