Intersection algorithm: Difference between revisions

Revision as of 12:10, 19 November 2024

Latest revision as of 18:03, 29 March 2025

(One intermediate revision by the same user not shown)

Line 3:

Equipment Corporation, 1989.</ref>

While Marzullo's algorithm will return the smallest interval consistent with the largest number of sources, the <ref name=":0" />returned interval does not necessarily include the center point (calculated offset) of all the sources in the intersection. The intersection algorithm returns an interval that includes that returned by Marzullo's algorithm but may be larger since it will include the center points. This larger interval allows using additional statistical data to select a point within the interval, reducing the [[jitter]] in repeated execution.

==Method==

Line 16:

<li> [initialize best f] Start with ''f''=0, assuming all input intervals are valid. Each time no interval is found f will be incremented until either an interval is found or ''f''&nbsp;≥&nbsp;''M''/2.</li>

<li> [initialize] ''endcount''=0 and ''midcount''=0.</li>

<li> [find lower endpoint] Start at beginning of the list (lowest offset) consider each tuple in order. ''endcount''&nbsp;=&nbsp;''endcount''&minus;''type''. If ''endcount''&nbsp;≥&nbsp;''M''&minus;''f'' then ''lower''&nbsp;=&nbsp;''offset'' and goto step 3 because the (possible) lower endpoint has been found. If the ''type''&nbsp;=&nbsp;0 then ''midcount''&nbsp;=&nbsp;''midcount''+1,. Repeat with next tuple. If reach end of list then goto step 6.</li>

<li> [tentative lower endpoint found, initialize to find upper endpoint] set ''endcount''=0. </li>

<li> [determine number of midpoints] Start from end of list and work towards lower offsets. ''endcount''&nbsp;=&nbsp;''endcount''+''type''. If ''endcount''&nbsp;≥&nbsp;''M''&minus;''f'' then ''upper''&nbsp;=&nbsp;''offset'', goto step 5. If ''type''&nbsp;=&nbsp;0 then ''midcount''&nbsp;=&nbsp;''midcount''+1,. Repeat for next tuple. If reach end of list then goto step 6.</li>

<li> if ''lower''&nbsp;≤&nbsp;''upper'' and ''midcount''&nbsp;≤&nbsp;''f'' then return interval [''lowerendpoint'', ''upperendpoint''] as resulting confidence interval.</li>

<li>[increment number of falsetickers] ''f''&nbsp;=&nbsp;''f''+1. If ''f''&nbsp;≥&nbsp;''M''/2 then terminate and return FAILED, otherwise goto step 1.</li>