8
$\begingroup$

Suppose that I want to optimize a unimodal function defined on some real interval. I can use the well-known algorithm as described in Wikipedia under the name of ternary search.

In case of the algorithm that repeatedly halving intervals, it is common to reserve the term binary search for discrete problems and to use the term bisection method otherwise. Extrapolating this convention, I suspect that the term trisection method might apply to the algorithm that solves my problem.

My question is whether it is common among academics, and is safe to use in, e.g., senior theses, to apply the term ternary search even if the algorithm is applied to a continuous problem. I need a reputable source for this. I'm also interested whether the term trisection method actually exists.

$\endgroup$
  • 1
    $\begingroup$ I don't know about the terminology, but why would you do that? There is not much time to be won by trisecting. $\endgroup$ – Raphael Jan 15 '14 at 8:35
  • 4
    $\begingroup$ I wouldn't worry about it. If Wikipedia calls it "ternary search", that's probably the most common name so use that. The worst that can happen is that your examiner recommends you change it to "trisection" throughout, as a minor correction. $\endgroup$ – David Richerby Jan 15 '14 at 10:01
  • $\begingroup$ @DavidRicherby I actually want to use "trisection" because it is consistent with the binary case. To do this I need to know the term is really used. $\endgroup$ – Pteromys Jan 16 '14 at 1:14
  • $\begingroup$ @Raphael The problem I'm concerned with is optimizing, not finding zeros, of functions. $\endgroup$ – Pteromys Jan 16 '14 at 1:15
  • 2
    $\begingroup$ @Pteromys It's more important to be consistent with standard usage than with some other case. Unless somebody confirms that "trisection" is used, stick with "ternary search" as that's the only term you have evidence for. (And, yeah, Google doesn't help because you get a million hits for people trying to subdivide angles.) "Trisection" may be a name with better justification but you're not in a position to invent new names for existing concepts. You could add a parenthetical remark but I wouldn't go farther than that without evidence of use. $\endgroup$ – David Richerby Jan 16 '14 at 1:26
0
$\begingroup$

The word "bitonic search" can probably refer to this concept. See this book and these lecture notes for instance.

$\endgroup$
  • $\begingroup$ I didn't know the word, but from the sources you've given I can only know that the term is used problems of a discrete domain. $\endgroup$ – Pteromys Jan 20 '14 at 10:55
  • 2
    $\begingroup$ You are right I had not noticed the emphasis on the continuity. Then how about Golden Section Search? $\endgroup$ – Hoda Jan 20 '14 at 16:31
  • $\begingroup$ thanks. The term "golden section search" seems to explicitly stand for the continuous case. However, it is reserved for a particular way of division of intervals. I'd like to divide intervals in another way. $\endgroup$ – Pteromys Jan 21 '14 at 0:39
  • 2
    $\begingroup$ @Pteromys, it can be shown (see Avriel and Wilde, "Optimality proof for the symmetric Fibonacci search technique", Fibonacci Quarterly 4:4, 265-269 (oct 1966)) that the Fibonacci search (closely related to the golden section search) is optimal if you only compare values for greater/smaller. $\endgroup$ – vonbrand Jan 29 '14 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.