Re: Minimal enclosing Triangle

How large is your 'n'?  As with some computational geometry
algorithms:
(1) The asymptotic behavior might not be noticeable until n
      is much larger than what your application uses.
(2) The effort to implement the algorithm is not worth the time
      when a simpler (but asymptotically slower) algorithm is
      easy to code.

I'm pretty sure the algorithm I mentioned is only a couple of factors
of n. I need pretty much real time performance, and the minimal
enclosing triangle algorithm isn't the only one being run.

I tried implementing the algorithm in "An Optimal Algorithm for
Finding Minimal Enclosing Triangles" (O'Rourke, Aggarwal, Maddila,
Baldwin) in Journal of Algorithms 7 (1986).
<snip>

I have browsed this paper but it appears that a careful reading is
essential to understand the pseudocode.

I managed to code it up in C++ and it seems to be OK with the polygons
I threw at it. For future reference and further comment, here's how I
interpreted the pseudocode in the OP.

If line 1 is true:

2.
side B is determined by [b-1, b]
vertex A is determined by side B and side C

3.
try side A using [a-1, a]
try vertex C from side A and side B
try midpoint of B from vertex A and vertex C
test if height(midpoint) < height(a-1)

4.
if not, vertex C is twice the height of a-1, but on side B
(essentially a mirror of the gamma(p) function, substituting side B
for side A for symmetry)

if line 1 is false:

5.
side B is determined by [gamma(b), b]
side A is determined by [gamma(b), a] (or [gamma(b), a-1], since
gamma(b) is on the line [a, a-1])
vertex C = gamma(b)
vertex A is determined by side B and side C
vertex B is determined by side A and side C

Cheers, G.
.

Relevant Pages

  • Re: Project help
    ... Low Power AES algorithm using VHDL ... in GALIOS FIELD and other parts of the algorithm like galios field ...   port( ...
    (comp.lang.vhdl)
  • Re: Lockfree flqueue and lockfree_mpmc ...
    ... and they all have the same problem under contention, ... MOV ECX, EAX ... there is a problem with this algorithm on the push and pop side... ...   then ...
    (comp.programming.threads)
  • Re: Project help
    ... Low Power AES algorithm using VHDL ... in GALIOS FIELD and other parts of the algorithm like galios field ...   port( ...
    (comp.lang.vhdl)
  • Re: Congruence based factoring algorithm
    ... algorithm will run faster with as small a p as possible; ...    report that T is prime ... Can you prove an upper bound on the numbers for which the effect can ... so it's equivalent to a brute force technique as a k that works gives ...
    (comp.theory)
  • Re: Searching substrings in records.
    ...     for each text field in the record ... but I just can't tell the difference between the algorithm ... you introduced above and the brute force approach I described on the ... every record and perform a substring search on any of them. ...
    (comp.programming)