On the Expected Performance of Path Compression Algorithms
We consider the expected running time of an equivalence algorithm using the path compression rule (but not the weighting rule). An $O(n)$ expected running time is proved for the execution of a random ...
We consider the expected running time of an equivalence algorithm using the path compression rule (but not the weighting rule). An $O(n)$ expected running time is proved for the execution of a random ...
Simplicity, Relativizations and Nondeterminism
Relativizations of complexity classes in which simple sets exist are considered. A recursive oracle is constructed relative to which a simple set exists for NP. Some other general theorems are proven,...
Relativizations of complexity classes in which simple sets exist are considered. A recursive oracle is constructed relative to which a simple set exists for NP. Some other general theorems are proven,...
You are not logged in to this journal. Log in
Finding Extremal Polygons
SIAM J. Comput. Volume 14, Issue 1, pp. 134-147 (1985)
Issue Date: 1985
Connotea
CiteULike
del.icio.us
BibSonomy
Given $n$ points in the plane, we present algorithms for finding maximum perimeter or area convex $k$-gons with vertices $k$ of the given $n$ points. Our algorithms work in linear space and time $O(kn\lg n + n\lg ^2 n)$. For the special case $k = 3$ we give $O(n\lg n)$ algorithms for these problems. Several related issues are discussed.
©1985 Society for Industrial and Applied Mathematics
| History: | Received 1982-06-23; accepted 1983-10-19 |
| Permalink: | http://dx.doi.org/10.1137/0214011 |
KEYWORDS and AMS
PUBLICATION DATA
0097-5397 (print)
1095-7111 (online)
SIAM