in computational geometry , many fundamental properties of finite point sets do not depend on the actual coordinates of each point in real space , but rather on the relative position of the points among each other . in their landmark paper ,
goodman and pollack   capture this idea by defining the order type of a point set . in the plane ,
two point sets have the same order type if there is a bijection  between the sets s.t . for every triple p , q , r of the first set , the corresponding points (p),(q ) , and (r ) have the same orientation ( i.e.
, are both oriented clockwise or counterclockwise).3 this orientation can be tested by the inequalitydet(pxpy1qxqy1rxry1)>0 , which indicates whether r is to the left of the directed line through p and q , i.e. , whether the triple is oriented counterclockwise .
the sign of the determinant therefore gives a predicate (p , q , r ) that is true iff the triple is oriented counterclockwise .
this mapping of all triples of a set to their orientation is also called the chirotope of the set ( cf . remark 1.6 in   and [ 3 , p. 95
many combinatorial properties of a set of points only depend on its order type , like its convex hull , the set of its crossing - free graphs , etc .
we implicitly assume throughout this paper that all sets are in general position , i.e. , do not contain collinear triples .
metric  properties of a point set that are not determined by the order type .
this includes the sets delaunay triangulation ; it is straightforward to construct two sets of the same order type whose delaunay triangulations are different .
guibas and stolfi   separate topological from geometric aspects , using a predicate incircle(p , q , r , s ) that is true iff the triple ( p , q , r ) is oriented counterclockwise and the point s lies inside the circle defined by the first three points .
their delaunay triangulation algorithm depends almost entirely on this predicate , making it a robust approach , that is intended to be easy to implement and to prove .
he defines five axioms over a ternary predicate p and calls sets of triples obeying them cc systems .
axiom 4interiorityp(t , p , q)p(t , q , r)p(t , r , p)p(p , q , r ) . 

axiom 5transitivityp(p , q , r)p(p , q , s)p(p , q , t)p(p , r , s)p(p , s , t ) 
 p(p , r , t ) .
p(t , p , q)p(t , q , r)p(t , r , p)p(p , q , r ) .
p(p , q , r)p(p , q , s)p(p , q , t)p(p , r , s)p(p , s , t ) 
 p(p , r , t ) .
these are fulfilled by all point sets in the euclidean plane , with p= defined as point triple orientation . for these sets ,
however , there exist cc systems that can not be constructed as point sets in r2 .
cc systems are equivalent to abstract order types , which , for example , can be used in so - called abstract order type extension 
 .
every abstract order type can be mapped to an arrangement of pseudo - lines in the projective plane .
a stretchable arrangement corresponds to a set of realizable order types [ 3 , pp .
goodman and pollack showed that all cc systems of up to 8 elements are realizable as point sets .
the concept of the convex hull of a point set generalizes to all cc systems .
the axiomatic approach can also be extended to cover delaunay triangulations . in the axiomatic settings ,
knuth provides o(nlogn ) time algorithms for both problems , where the time bound for the latter holds in the expected case .
he points out that the algorithm of guibas and stolfi uses the coordinate representation to find a line that partitions the point set into two equally sized subsets ( cf .
9798 ] therefore asks for an algorithm to find such a partition of a cc system in linear time .
the problem is straightforward when given an extreme point of the set ( i.e. , an element of the convex hull boundary ) .
proving the existence of a linear - time algorithm for finding a single extreme point is also explicitly part of open problem 1 . in this work
, we answer both parts of the open problem in the affirmative . in section 2
, we give a simple o(n ) time algorithm that , given a point c of a set s of size n , finds a halving edge through c ; more specifically , it finds a second point cs s.t .
not more than n22 points are on each side of the supporting line of c and c. we then describe in section 3 an algorithm that , given two points p and q , returns the edge of the convex hull that is crossed by the ray from p through q. we first show that the algorithm runs in o(n ) time for realizable sets .
we then show that the time bound is also correct for non - realizable sets , that is , for all cc systems .
our main motivation is to show that the asymptotic running time for solving these problems does not depend on the representation by coordinates . while an arbitrary halving edge can easily be found by picking a point with median ,
say , x - coordinate , the problem is more sophisticated when the halving line should pass through a predefined point .
e.g. , the linear time ham - sandwich - cut algorithm of lo , matouek and steiger   can be adapted to find a halving line through a point .
the straightforward way of finding an extreme point of a set given by coordinates is selecting the one with , say , lowest x - coordinate .
finding a convex hull edge that is traversed by a given line in linear time is a subroutine of the so - called ultimate convex hull algorithm of kirkpatrick and seidel .
there , the median of the slopes of an arbitrary matching of the points is used for the prune and search approach .
recent algorithms that operate only on triple orientations involve computing the convex hull of disks .
also note that there are models that allow for more abstract order types to be realized than by point sets in the euclidean plane . a preliminary version of this work appeared as .
in this section we describe an algorithm to compute a halving edge through a given point c of a finite point set s of size n in the plane . while we give the algorithm for realizable order types , note throughout the proof that all assumptions also hold in the abstract setting .
the idea is to split the point set evenly by two double wedges centered at c. we identify the double wedge that must contain a halving edge , and continue with the points therein .
imagine a directed line  rotated by 180 clockwise around c , starting at p1 .
let p2,  ,pn1 be the remaining points in the order  passes through them , either with its front or its tail .
we denote this order by  , which is actually the order described in [ 3 , p. 16
for each pair of s{c } , we can compute the relative order in which  passes through them in constant time , using the predicate . thus the median m = pn2 with respect to  can be computed in o(n ) time .
( note that the number of points to the right of  may not change monotonically while rotating . )
the supporting lines of cp1 and cm define two double wedges , containing s1={ps{c}:pm } and s2={ps{c}:mp } , respectively , each having not more than n22 points .
more than n22 points to the right of 1 and thus less than n22 points to the right of n . due to our general position assumption , while rotating  only one point changes sides at the same time .
if less than n22 points are right of n2 , then one of the points in s1 forms a halving edge with c ( recall that there are w.l.o.g .
. otherwise one of the points in s2 does . this way we can decide which subset contains a halving edge , exclude the other subset and iterate . observe that all the points we exclude belong to two ( open ) wedges centered at c , one entirely to the left and one entirely to the right of the non - removed lines of 2,  ,n1 .
the closure of each wedge contains a ray of 1 . we store how many points each of these wedges contained .
now , if we want to compute the number of points to the right of some line i in subsequent iterations , then we only need to consider the remaining points and add the number of points belonging to the excluded wedge to the right of i .
the algorithm has linear running time , as we exclude approximately half of the points in each linear - time iteration .
theorem 2given a point set 
 sr2 
 of size n in general position and a point 
 cs , a halving edge of s incident to c can be found in linear time using only the predicate . given a point set 
 sr2 
 of size n in general position and a point 
 cs , a halving edge of s incident to c can be found in linear time using only the predicate . now we argue that the above approach does not require that s is realizable , that is , it works for any cc system ( using the predicate p ) .
the order  around c we use is also defined for cc systems by signing the points in a way that the positive points are to the right of 1 and the negative ones are to the left of 1 , where each negative sign will change the orientation of a triple containing c 
 [ 3 , p. 16
this allows us to give a purely combinatorial formulation of our algorithm : let s be a variable initialized to 0 and let ri be the number of negative points preceding point pi plus the number of positive points succeeding pi with respect to  in the current iteration ( this corresponds to the points to the right of i ) .
if the sum of rm and s is less than n22 , we remove the points that succeed m , and add the number of removed positive points to s. otherwise , we remove the points that precede m and add the number of removed negative points to s. note that for every point pi , the value of ri+s is an invariant over all iterations .
eventually , we end up with an element pj such that rj+s=n22. in the combinatorial formulation of the algorithm , the crucial properties of the sequence r we use is that subsequent elements change by one and that the required value is between r1 and rn .
therefore , the algorithm is also adaptable to more sophisticated problems than finding a halving edge .
one example is the search for a balanced line , that is , a line that separates a set consisting of n white points and n black points in a way that the difference between the black and white points on each side of the line is 0 ( additional care has to be taken when defining the sequence r since a balanced line does in general not pass directly through a given point c , i.e. , there is no explicit representation of the line as a supporting line of two points ) .
there , it is shown that certain crossing - free matchings on a point set are not unique by constructing a balanced line crossing a segment of a given matching . for realizable sets ,
for the oriented hyperplane h through the points ( p1,  ,pd ) , (p1, 
corollary 3given a point set 
 srd 
 in general position , d constant , and distinct points 
 c1,  ,cd1s , one can find a halving hyperplane through 
 c1, 
,cd1 
 in linear time using only . given a point set 
 srd 
 in general position , d constant , and distinct points 
 c1,  ,cd1s , one can find a halving hyperplane through 
 c1, 
in this section we show how to compute a convex hull edge of a set in linear time , only using the orientation of triples .
we first present the algorithm for point sets and then extend it to general cc systems . as a first step we describe an algorithm called basicmin , which plays a crucial role as a subroutine .
let s be a point set in the plane and suppose we are given two points p , rs .
let r be the coordinate origin and let p be on the positive part of the x - axis .
let m be an arbitrary perfect matching between the points above and below the x - axis , i.e. , for any edge s = abm we have (p , r , a)(p , r , b ) .
let  be the binary operator that accepts two edges s , sm as input and returns the edge on the convex hull boundary of ss that crosses the x - axis at the smallest x - coordinate , i.e. , the pair of endpoints whose upward - directed supporting line has all other points of s and s to the right .
the relevant property of the operator is that the crossing of (s , s ) with the x - axis is not to the right of the crossings of s and s with the x - axis .
basicmin takes a point set s and two points p and r as input , partitions s arbitrarily into the matching m={s1, 
,s(n22 ) } , and computes a special edge m = m(n22 ) iteratively viam1=s1,m(i+1)=(mi , s(i+1 ) ) .
obviously , the running time of basicmin is linear in n. note that m does not need to be on the convex hull of the whole set .
also , m may depend on the ( undefined ) order in which the elements of m are processed by basicmin .
lemma 4let  be a line directed upwards , crossing the x - axis left of the crossing of m with the x - axis .
then at least 
 n22 
 points of s are to the right of . 
 proofnote that the crossing of  with the x - axis is further to the left than any other such crossing of m. assume , for the purpose of contradiction , that there is an edge in m for which both points lie to the left of . then also the crossing with the x - axis is to the left of the crossing of m , a contradiction .
hence , for each of the n22 edges in m at least one endpoint lies to the right of .   let  be a line directed upwards , crossing the x - axis left of the crossing of m with the x - axis .
then at least 
 n22 
 points of s are to the right of . note that the crossing of  with the x - axis is further to the left than any other such crossing of m. assume , for the purpose of contradiction , that there is an edge in m for which both points lie to the left of . then also the crossing with the x - axis is to the left of the crossing of m , a contradiction .
hence , for each of the n22 edges in m at least one endpoint lies to the right of .   note that , even though the argumentation of lemma 4 involves relative positions of crossings , the constant - time operation  can be expressed by using only . now we are ready to give the main algorithm .
theorem 5given two points 
 p , q 
 of a point set 
 sr2 
 of size n in general position , one can find the edge e of the sets convex hull that passes through the ray pq in 
 o(n ) 
 time using the predicate . 
 proofw.l.o.g .
let pq be horizontal with q left of p. note first that the case where q is a vertex of the convex hull can be identified in linear time .
we therefore concentrate on the setting where one endpoint of e is below pq and the other one is above .
let u be the set strictly above pq , whereas l is the set strictly below pq .
w.l.o.g . let |u|n22.consider the endpoint u1u of e. if we remove u1 , the ray pq intersects the boundary of the ( new ) convex hull at a new edge e with an endpoint u2u .
note that the other endpoint of e might now be q. in any case , iteratively removing points from u of the intersected convex hull edge induces an order on u ( see fig .
4 ) . note that this corresponds to the order in which the points of u are traversed by a tangent t of ch(l{p , q } ) that is rotated clockwise around that hull , starting at e and ending at pq .
the main observation is that in the search for u1 , given a point ui and the tangent t passing through ui , we can discard all points of u to the right of ui with respect to the point
l where t touches ch(l{p , q } ) , since none of these points can be u1 .
the support ll{q } of t can be found in linear time , since the radial order of l{p , q } around any ui is linear.note that these observations already imply the following randomized approach .
the other support l of the tangent ( recall that this might as well be q ) can be found in linear time . we discard the points of u right of lui and iterate .
however , consecutive  bad  choices of ui result in overall quadratic worst - case behavior .
we therefore have to make a  good  choice of ui in order to discard a linear number of points per iteration.the points of u are ordered linearly around p. let ur be the median of this order , which we select in linear time .
let m be an arbitrary perfect matching between the points of u to the left and to the right of pur ( maybe omitting one point ) , see fig .
now we apply basicmin on m with r = ur , which results in an edge m = uaub . by construction , all edges of m as well as uaub cross the ray pur . now , find the tangents ta and tb of ch(l{p , q } ) through ua and ub , respectively ( we consider them being directed upwards )
. let =ta if ub is to the right of ta , otherwise let =tb . note that p is right of  since q is included in the set that we place the tangent on .
if  crosses the ray pur at a point x , then the crossing of uaub is on the ray between p and x ( by definition of  ) . due to lemma 4 ,
at least half of the points of m are to the right of . otherwise , if  does not cross the ray pur , then all points of u to the right of the ray are also to the right of . in both cases , we can discard at least half of the points , which is at least a quarter of the overall set s ( recall that u was w.l.o.g .
larger than l ; in each iteration , the process is applied to the larger of the two sets ) .
we can therefore in linear time reduce this problem to constant size such that it then can be solved by a brute - force approach . 
 given two points 
 p , q 
 of a point set 
 sr2 
 of size n in general position , one can find the edge e of the sets convex hull that passes through the ray pq in 
 o(n ) 
 time using the predicate . w.l.o.g .
let pq be horizontal with q left of p. note first that the case where q is a vertex of the convex hull can be identified in linear time .
we therefore concentrate on the setting where one endpoint of e is below pq and the other one is above .
let u be the set strictly above pq , whereas l is the set strictly below pq .
consider the endpoint u1u of e. if we remove u1 , the ray pq intersects the boundary of the ( new ) convex hull at a new edge e with an endpoint u2u .
note that the other endpoint of e might now be q. in any case , iteratively removing points from u of the intersected convex hull edge induces an order on u ( see fig .
4 ) . note that this corresponds to the order in which the points of u are traversed by a tangent t of ch(l{p , q } ) that is rotated clockwise around that hull , starting at e and ending at pq .
the main observation is that in the search for u1 , given a point ui and the tangent t passing through ui , we can discard all points of u to the right of ui with respect to the point
l where t touches ch(l{p , q } ) , since none of these points can be u1 .
the support ll{q } of t can be found in linear time , since the radial order of l{p , q } around any ui is linear .
the other support l of the tangent ( recall that this might as well be q ) can be found in linear time .
we discard the points of u right of lui and iterate . however , consecutive  bad  choices of ui result in overall quadratic worst - case behavior .
we therefore have to make a  good  choice of ui in order to discard a linear number of points per iteration .
the points of u are ordered linearly around p. let ur be the median of this order , which we select in linear time .
let m be an arbitrary perfect matching between the points of u to the left and to the right of pur ( maybe omitting one point ) , see fig .
5 . now we apply basicmin on m with r = ur , which results in an edge m = uaub . by construction ,
all edges of m as well as uaub cross the ray pur . now , find the tangents ta and tb of ch(l{p , q } ) through ua and ub , respectively ( we consider them being directed upwards ) .
let =ta if ub is to the right of ta , otherwise let =tb . note that p is right of  since q is included in the set that we place the tangent on .
if  crosses the ray pur at a point x , then the crossing of uaub is on the ray between p and x ( by definition of  ) . due to lemma 4 ,
at least half of the points of m are to the right of . otherwise , if  does not cross the ray pur , then all points of u to the right of the ray are also to the right of . in both cases , we can discard at least half of the points , which is at least a quarter of the overall set s ( recall that u was w.l.o.g .
larger than l ; in each iteration , the process is applied to the larger of the two sets ) .
we can therefore in linear time reduce this problem to constant size such that it then can be solved by a brute - force approach . 
 note that the transitivity of the order on u directly follows from the definition of the convex hull and carries over to general cc systems .
also , the transitivity of l{p , q } around any point of u holds for cc systems due to axiom 5 .
however , the linear time bound depends on the number of points that are to the right of . in order to show that the bound also holds for abstract order types , we need to prove that basicmin also works as expected on non - realizable sets , and that then also  has at least half of the points of u to the right .
there exist several equivalent definitions for the convex hull of a finite point set s in the plane .
for example , the convex hull can be defined as the convex polygon of smallest area that contains all points of the set .
equivalently , the boundary of the convex hull of s is the sequence of pairs uv with { u , v}s such that all points s{u , v } are to the left of uv .
this latter definition is more combinatorial and carries over to the abstract setting , where we are no longer concerned with 
geometric artefacts  like area or perimeter.4 in this subsection , we will give a brief summary of the relevant properties of abstract order types , following goodman and pollack , which we suggest to the reader for further information on that topic , in addition to . throughout this section ,
let us again start in the euclidean plane by considering a point set s , which we still require , for ease of presentation , to be in general position ( see   on how to handle other cases ) .
let  be a directed line not orthogonal to any supporting line of s. project the points orthogonally on  , which gives us a sequence of the points along . if we rotate  in counterclockwise direction , then eventually two points , let them be u and v , will happen to be projected to the same point on . when continuing the rotation process , u and v will have changed their position in the sequence along . after a rotation of 180 , the initial sequence of the projected points on  will be reversed .
continuing the rotation gives an infinite periodic sequence of transpositions like the one of u and v. it is called the circular sequence of permutations associated to s , or the circular sequence of s , for short .
one can observe that after a reversal of u and v all other pairs are reversed until u and v are reversed again .
the circular sequence allows us to observe several geometric properties of s. a point that precedes all others in some permutation ( on  ) in the circular sequence is an extreme point .
note that all the information we can get from the circular sequence is encoded in one half - period .
we therefore can identify the vertices of the convex hull as those points that are topmost or bottommost on  at some point , when we look at  such that it is directed downwards .
for every subset of s , the circular sequence therefore gives the point on its convex hull .
consider again the moment when u and v change their position in the permutation , say from uv to vu .
then the triple uvw is oriented counterclockwise if and only if w is projected below ( i.e. , after ) both u and v when they change their position ( assuming counterclockwise rotation of  ) .
note that this requires that at the beginning of the half - period u is above ( before ) v. it is common and convenient to identify the points of s with their order at the initial position of . for s={p1,  ,pn } , we therefore start with pi above pj on  iff i < j .
while the starting position of  in the half - period is arbitrary , this labeling is useful when comparing point triples .
after a half - period , the points are given in the sequence pn,  ,p1. the circular sequence contains strictly more information than the order type of a set .
while the order type is implied by the circular sequence , it is rather straightforward to construct point sets with different circular sequences that have the same order type .
consider an arrangement of pseudo - lines in the projective plane p2 ( a set of closed curves not separating p2 that pairwise intersect in exactly one point ) .
an arrangement is simple if no three pseudo - lines intersect in one point . one important property of pseudo - line arrangements , shown by levi , is that they can be extended by additional pseudo - lines .
lemma 6levi enlargement lemmagiven a pseudo - line arrangement 
 a 
 in 
 p2 
 and two points that do not both lie on the same element of 
 a , there exists a pseudo - line arrangement 
 a{ } 
 such that the pseudo - line  passes through these two points . given a pseudo - line arrangement 
 a 
 in 
 p2 
 and two points that do not both lie on the same element of 
 a
, there exists a pseudo - line arrangement 
 a{ } 
 such that the pseudo - line  passes through these two points . using this lemma ,
choose a pseudo - line  not part of the arrangement as the line at infinity .
place a point  on . if we choose  as the point at vertical infinity , we can identify the arrangement of pseudo - lines with an arrangement of x - monotone pseudo - lines in the euclidean plane ( where the curves are no longer closed ) .
this requires the application of the levi enlargement lemma to get x - monotonicity , details are given in .
if we sweep this arrangement from left to right , we get again a half - period of a circular sequence , where a change of a pair happens as we sweep across the intersection of two pseudo - lines .
goodman and pollack   show that any circular sequence of a point set describes the topology of an arrangement of pseudo - lines in p2 .
actually , for every point set in the euclidean plane , the standard duality transform for point sets gives an arrangement of straight lines whose crossings , when sweeping from left to right , give a half - period of the circular sequence of the set .
there are , however , arrangements of pseudo - lines in the projective plane that are not stretchable . for them , no point set in the euclidean plane exists that implies any sequence derived from such an arrangements by any choice of . recall that we were able to derive the orientation of a point triple uvw by the position of the points in a half - period of the circular sequence . given a direction around a point at infinity allows us to give a triple of pseudo - lines an orientation , even if there does not exist a corresponding point set order type in the euclidean plane ( i.e. , the sequence is non - realizable ) ; we still get a predicate a that gives each triple an orientation , that is , an abstract order type .
knuth   shows that , for any simple arrangement , a fulfills the five axioms defining cc systems , and from any cc system a corresponding arrangement can be derived ; hence , the terms  cc system  and  abstract order type  are merely synonyms .
we can use either the axioms or a pseudo - line arrangement ( together with a direction around a point at infinity ) for arguing about abstract order types . in the next section
, we will use the model of x - monotone pseudo - lines in the euclidean plane . at first sight , the identification of abstract order types with pseudo - line arrangements in the projective plane might feel like a detour to x - monotone arrangements in the euclidean plane as representation of circular sequences .
this might be the case for the application of the concept in this paper , however , it is profound in the whole theory about abstract order types . recall that different circular sequences might correspond to two point sets having the same order type .
( on the other hand , for arrangements of pseudo - lines in the projective plane , there are transformations that are order - type - preserving and some that are not . )
if two pairs uv and st of four different points change their position in the sequence and uv happens right before st in the half - period , then changing st right before uv results in the same order type .
( to reduce the cases to consider , we will nevertheless make use of that relative position of pseudo - line crossings in the next section .
) there is another aspect that is not directly captured by x - monotone arrangements in the euclidean plane .
when mapping the arrangement from the projective to the euclidean plane , we chose the line at infinity through  arbitrarily ; however , the topology of the arrangement in the projective plane does not depend on the choice of this line .
analogously , the circular sequence of a point set does not depend on the actual starting position of . in terms of pseudo - lines in the euclidean plane , the following can be shown ( more details are given in ) .
consider a crossing of two pseudo - lines that has no further crossings to the left from its initial position .
then we can move this crossing to the right end of the arrangement , such that the resulting arrangement still represents the same abstract order type .
in other words , we  untangle  the crossing at the left end and introduce a new one to the right ( note that this corresponds to removing the position change uv at the beginning by a change vu at the end ) . for every abstract order type and any crossing therein , we can therefore choose a x - monotone representation where that crossing is leftmost . to see why care has to be taken when we deal with non - realizable order types , note that in general the order type does not capture the relative position of the supporting lines of point pairs and the crossings of these lines .
however , abstract order types capture some of the information that is related to crossings of supporting lines , which allows us to show that the properties needed for basicmin are also present in the abstract setting.5 we use the dual representation of abstract order types in the euclidean plane by x - monotone pseudo - lines ; this allows us to use the obvious meaning of terms like  above  and  below  when describing an arrangement a ( e.g. , a pseudo - line a is above a point b when the point on a that has the same x - coordinate as b has a larger y - coordinate than b ) .
we are given a set s of n elements ( which we call points , even though s might not be a realizable point set ) , containing two special points p and q. the set s is separated by pq into a set u to the right of pq , and a set l to the left of it ( where  left  and  right  are indicated by a predicate a ) .
we want to obtain the pair l1u1,l1l , u1u that is consecutive on the convex hull of s , where p is to the right of l1u1 .
this is done by obtaining a pair =ljui such that at least half of the points of u ( minus a constant ) are to the right of  and no point of l is to the left of . consider the dual x - monotone pseudo - line arrangement a representing the abstract order type of s. keep in mind that p is an extreme point of the set u{p } , and that r = ur is the median of the points in u ordered radially around p. we can represent the arrangement such that the crossing of the pseudo - lines p and r ( which corresponds to the supporting line of pr in the primal6 ) is the leftmost crossing in the x - monotone representation of a. the linear order of the points around p in the primal splits the set u{ur } into left and right points , separated by pr . in the dual , the right pseudo - lines pass above the crossing pr , and the left pseudo - lines pass below .
the operator  accepts two point pairs , each pair consisting of a left and a right point .
the output of the operator is a pair z consisting of a left and a right point such that all other points are to the right of the oriented line through these points .
this pair z is well - defined in the abstract setting as well ( and there is always a geometric representation due to theorem 1 ) . recall that we compute a special pair m = m(n22 ) iteratively viam1=s1,m(i+1)=(mi , s(i+1 ) ) .
the crucial property of the pair m = uaub ( and later the line  tangent to ch(l{p , q } ) through ua or ub ) is that at least one endpoint of each pair sim lies on the same side of m as the pivot p. ( we assume that m and the elements of m are directed from the left point to the right point and hence p is to the right of m. ) in the dual , each element of m is represented as the crossing of a right and a left pseudo - line in a ( this corresponds to the supporting line of the matched pair of points in the primal ) .
the crucial property for m in the dual therefore is to have at least one pseudo - line of each pair sim passing below its crossing in a. for realizable point sets , we were able to argue for the correctness of basicmin using the intersection  of a matched pair s with the supporting line of p and r. in the dual , this intersection  corresponds again to a pseudo - line that can be added to a ; this pseudo - line passes through the crossing pr and s. also for non - realizable sets , such a pseudo - line  exists due to the levi enlargement lemma .
in fact , in non - realizable settings the intersections behave in the same transitive manner as in the realizable setting ; see fig . 7 for an illustration of the following statement .
observation 7let 
 z=(a , b ) 
 and 
 z=(c , d ) 
 be two pairs such that the point p is to the right of both pairs ( i.e. , in the dual the pseudo - line p is below the crossings z and 
 z ) .
let  (  ) be a dual pseudo - line through the crossings pr and z ( z ) .
if none of a and b is to the left of the primal line 
 z , then the dual pseudo - line 
  
 is above  in the part of the dual arrangement that is to the right of the dual crossing pr .
let 
 z=(a , b ) 
 and 
 z=(c , d ) 
 be two pairs such that the point p is to the right of both pairs ( i.e. , in the dual the pseudo - line p is below the crossings z and 
 z ) .
let  (  ) be a dual pseudo - line through the crossings pr and z ( z ) .
if none of a and b is to the left of the primal line 
 z , then the dual pseudo - line 
  
 is above  in the part of the dual arrangement that is to the right of the dual crossing pr .
hence , after applying basicmin to the matching m , we obtain in the dual a pseudo - line crossing m on a pseudo - line m that passes through the crossing pr , such that no crossing of m is above m .
suppose , for the sake of contradiction , that there is a pair ( a , b ) such that both dual pseudo - lines a and b pass above the crossing m , but the crossing ab is below m . if the crossing ab is to the left of m in the x - monotone arrangement , then , when traversing a from left to right , one would have to pass below m and then go above it again before m. otherwise , if the crossing ab is to the right of m , then b would have to intersect m to be above it at m and then has to be below m again to reach the crossing ab .
both cases contradict the fact that a pair of pseudo - lines intersects exactly once in the x - monotone arrangement .
hence , half of the pseudo - lines are below the pseudo - line crossing m in a. this corresponds to at least half of the points being on the same side of m as p. recall that in the proof of theorem 5 , we chose a directed line  supported by a point ll{q } and either ua or ub such that no elements of l{p , q , ua , ub } is to the left of it .
we now proceed to show that at least one point of each pair ( v , w ) in m is to the right of the directed line  , as demanded in the proof of theorem 5 .
the points involved are { p , q , r , l , ua , ub , v , w } , where l and q might be the same point .
since these are at most eight points , we are allowed to use geometric arguments due to theorem 1 .
however , we must not rely on the positions of the crossing points on the ray pr .
suppose , for the sake of contradiction , that neither of v and w is right of . at least one of v or w has to be to the right of uaub .
these observations imply that vw is an edge of the convex hull of { p , ua , ub , v , w}. however , this means that the crossing of the pseudo - lines v and w is above ua and ub in a , which contradicts the fact that uaub is m. thus , we conclude theorem 8theorem 5 
 also holds for non - realizable cc systems , i.e. , abstract order types .
theorem 5 
 also holds for non - realizable cc systems , i.e. , abstract order types .
as a first step we describe an algorithm called basicmin , which plays a crucial role as a subroutine . let s be a point set in the plane and suppose we are given two points p , rs .
let r be the coordinate origin and let p be on the positive part of the x - axis .
let m be an arbitrary perfect matching between the points above and below the x - axis , i.e. , for any edge s = abm we have (p , r , a)(p , r , b ) .
let  be the binary operator that accepts two edges s , sm as input and returns the edge on the convex hull boundary of ss that crosses the x - axis at the smallest x - coordinate , i.e. , the pair of endpoints whose upward - directed supporting line has all other points of s and s to the right .
the relevant property of the operator is that the crossing of (s , s ) with the x - axis is not to the right of the crossings of s and s with the x - axis .
basicmin takes a point set s and two points p and r as input , partitions s arbitrarily into the matching m={s1, 
,s(n22 ) } , and computes a special edge m = m(n22 ) iteratively viam1=s1,m(i+1)=(mi , s(i+1 ) ) . obviously , the running time of basicmin is linear in n. note that m does not need to be on the convex hull of the whole set .
also , m may depend on the ( undefined ) order in which the elements of m are processed by basicmin .
lemma 4let  be a line directed upwards , crossing the x - axis left of the crossing of m with the x - axis .
then at least 
 n22 
 points of s are to the right of . 
 proofnote that the crossing of  with the x - axis is further to the left than any other such crossing of m. assume , for the purpose of contradiction , that there is an edge in m for which both points lie to the left of . then also the crossing with the x - axis is to the left of the crossing of m , a contradiction .
hence , for each of the n22 edges in m at least one endpoint lies to the right of .   let  be a line directed upwards , crossing the x - axis left of the crossing of m with the x - axis .
then at least 
 n22 
 points of s are to the right of . note that the crossing of  with the x - axis is further to the left than any other such crossing of m. assume , for the purpose of contradiction , that there is an edge in m for which both points lie to the left of . then also the crossing with the x - axis is to the left of the crossing of m , a contradiction .
hence , for each of the n22 edges in m at least one endpoint lies to the right of .   note that , even though the argumentation of lemma 4 involves relative positions of crossings , the constant - time operation  can be expressed by using only . now we are ready to give the main algorithm .
theorem 5given two points 
 p , q 
 of a point set 
 sr2 
 of size n in general position , one can find the edge e of the sets convex hull that passes through the ray pq in 
 o(n ) 
 time using the predicate . 
 proofw.l.o.g .
let pq be horizontal with q left of p. note first that the case where q is a vertex of the convex hull can be identified in linear time .
we therefore concentrate on the setting where one endpoint of e is below pq and the other one is above .
let u be the set strictly above pq , whereas l is the set strictly below pq .
w.l.o.g . let |u|n22.consider the endpoint u1u of e. if we remove u1 , the ray pq intersects the boundary of the ( new ) convex hull at a new edge e with an endpoint u2u .
note that the other endpoint of e might now be q. in any case , iteratively removing points from u of the intersected convex hull edge induces an order on u ( see fig .
4 ) . note that this corresponds to the order in which the points of u are traversed by a tangent t of ch(l{p , q } ) that is rotated clockwise around that hull , starting at e and ending at pq .
the main observation is that in the search for u1 , given a point ui and the tangent t passing through ui , we can discard all points of u to the right of ui with respect to the point
l where t touches ch(l{p , q } ) , since none of these points can be u1 .
the support ll{q } of t can be found in linear time , since the radial order of l{p , q } around any ui is linear.note that these observations already imply the following randomized approach .
the other support l of the tangent ( recall that this might as well be q ) can be found in linear time .
we discard the points of u right of lui and iterate . however , consecutive  bad  choices of ui result in overall quadratic worst - case behavior .
we therefore have to make a  good  choice of ui in order to discard a linear number of points per iteration.the points of u are ordered linearly around p. let ur be the median of this order , which we select in linear time .
let m be an arbitrary perfect matching between the points of u to the left and to the right of pur ( maybe omitting one point ) , see fig .
5 . now we apply basicmin on m with r = ur , which results in an edge m = uaub . by construction , all edges of m as well as uaub cross the ray pur .
now , find the tangents ta and tb of ch(l{p , q } ) through ua and ub , respectively ( we consider them being directed upwards )
. let =ta if ub is to the right of ta , otherwise let =tb . note that p is right of  since q is included in the set that we place the tangent on .
if  crosses the ray pur at a point x , then the crossing of uaub is on the ray between p and x ( by definition of  ) . due to lemma 4 ,
at least half of the points of m are to the right of . otherwise , if  does not cross the ray pur , then all points of u to the right of the ray are also to the right of . in both cases , we can discard at least half of the points , which is at least a quarter of the overall set s ( recall that u was w.l.o.g .
larger than l ; in each iteration , the process is applied to the larger of the two sets ) .
we can therefore in linear time reduce this problem to constant size such that it then can be solved by a brute - force approach . 
 given two points 
 p , q 
 of a point set 
 sr2 
 of size n in general position , one can find the edge e of the sets convex hull that passes through the ray pq in 
 o(n ) 
 time using the predicate . w.l.o.g .
let pq be horizontal with q left of p. note first that the case where q is a vertex of the convex hull can be identified in linear time .
we therefore concentrate on the setting where one endpoint of e is below pq and the other one is above .
let u be the set strictly above pq , whereas l is the set strictly below pq .
consider the endpoint u1u of e. if we remove u1 , the ray pq intersects the boundary of the ( new ) convex hull at a new edge e with an endpoint u2u .
note that the other endpoint of e might now be q. in any case , iteratively removing points from u of the intersected convex hull edge induces an order on u ( see fig .
4 ) . note that this corresponds to the order in which the points of u are traversed by a tangent t of ch(l{p , q } ) that is rotated clockwise around that hull , starting at e and ending at pq .
the main observation is that in the search for u1 , given a point ui and the tangent t passing through ui , we can discard all points of u to the right of ui with respect to the point
l where t touches ch(l{p , q } ) , since none of these points can be u1 . the support ll{q } of t can be found in linear time , since the radial order of l{p , q } around any ui is linear .
the other support l of the tangent ( recall that this might as well be q ) can be found in linear time .
however , consecutive  bad  choices of ui result in overall quadratic worst - case behavior .
we therefore have to make a  good  choice of ui in order to discard a linear number of points per iteration .
the points of u are ordered linearly around p. let ur be the median of this order , which we select in linear time .
let m be an arbitrary perfect matching between the points of u to the left and to the right of pur ( maybe omitting one point ) , see fig .
5 . now we apply basicmin on m with r = ur , which results in an edge m = uaub . by construction , all edges of m as well as uaub cross the ray pur .
now , find the tangents ta and tb of ch(l{p , q } ) through ua and ub , respectively ( we consider them being directed upwards )
. let =ta if ub is to the right of ta , otherwise let =tb . note that p is right of  since q is included in the set that we place the tangent on .
there are two cases to consider . if  crosses the ray pur at a point x , then the crossing of uaub is on the ray between p and x ( by definition of  ) . due to lemma 4 ,
at least half of the points of m are to the right of . otherwise , if  does not cross the ray pur , then all points of u to the right of the ray are also to the right of . in both cases , we can discard at least half of the points , which is at least a quarter of the overall set s ( recall that u was w.l.o.g .
larger than l ; in each iteration , the process is applied to the larger of the two sets ) .
we can therefore in linear time reduce this problem to constant size such that it then can be solved by a brute - force approach . 
 note that the transitivity of the order on u directly follows from the definition of the convex hull and carries over to general cc systems .
also , the transitivity of l{p , q } around any point of u holds for cc systems due to axiom 5 .
however , the linear time bound depends on the number of points that are to the right of . in order to show that the bound also holds for abstract order types , we need to prove that basicmin also works as expected on non - realizable sets , and that then also  has at least half of the points of u to the right .
there exist several equivalent definitions for the convex hull of a finite point set s in the plane .
for example , the convex hull can be defined as the convex polygon of smallest area that contains all points of the set .
equivalently , the boundary of the convex hull of s is the sequence of pairs uv with { u , v}s such that all points s{u , v } are to the left of uv .
this latter definition is more combinatorial and carries over to the abstract setting , where we are no longer concerned with  geometric artefacts  like area or perimeter.4 in this subsection , we will give a brief summary of the relevant properties of abstract order types , following goodman and pollack , which we suggest to the reader for further information on that topic , in addition to . throughout this section ,
let us again start in the euclidean plane by considering a point set s , which we still require , for ease of presentation , to be in general position ( see   on how to handle other cases ) .
let  be a directed line not orthogonal to any supporting line of s. project the points orthogonally on  , which gives us a sequence of the points along . if we rotate  in counterclockwise direction , then eventually two points , let them be u and v , will happen to be projected to the same point on . when continuing the rotation process , u and v will have changed their position in the sequence along . after a rotation of 180 , the initial sequence of the projected points on  will be reversed .
continuing the rotation gives an infinite periodic sequence of transpositions like the one of u and v. it is called the circular sequence of permutations associated to s , or the circular sequence of s , for short .
one can observe that after a reversal of u and v all other pairs are reversed until u and v are reversed again .
the circular sequence allows us to observe several geometric properties of s. a point that precedes all others in some permutation ( on  ) in the circular sequence is an extreme point .
note that all the information we can get from the circular sequence is encoded in one half - period .
we therefore can identify the vertices of the convex hull as those points that are topmost or bottommost on  at some point , when we look at  such that it is directed downwards .
for every subset of s , the circular sequence therefore gives the point on its convex hull .
consider again the moment when u and v change their position in the permutation , say from uv to vu .
then the triple uvw is oriented counterclockwise if and only if w is projected below ( i.e. , after ) both u and v when they change their position ( assuming counterclockwise rotation of  ) .
note that this requires that at the beginning of the half - period u is above ( before ) v. it is common and convenient to identify the points of s with their order at the initial position of . for s={p1,  ,pn } , we therefore start with pi above pj on  iff i < j . while the starting position of  in the half - period is arbitrary , this labeling is useful when comparing point triples .
after a half - period , the points are given in the sequence pn,  ,p1. the circular sequence contains strictly more information than the order type of a set .
while the order type is implied by the circular sequence , it is rather straightforward to construct point sets with different circular sequences that have the same order type .
consider an arrangement of pseudo - lines in the projective plane p2 ( a set of closed curves not separating p2 that pairwise intersect in exactly one point ) .
an arrangement is simple if no three pseudo - lines intersect in one point . one important property of pseudo - line arrangements , shown by levi , is that they can be extended by additional pseudo - lines .
lemma 6levi enlargement lemmagiven a pseudo - line arrangement 
 a 
 in 
 p2 
 and two points that do not both lie on the same element of 
 a , there exists a pseudo - line arrangement 
 a{ } 
 such that the pseudo - line  passes through these two points . given a pseudo - line arrangement 
 a 
 in 
 p2 
 and two points that do not both lie on the same element of 
 a
, there exists a pseudo - line arrangement 
 a{ } 
 such that the pseudo - line  passes through these two points .
using this lemma , choose a pseudo - line  not part of the arrangement as the line at infinity .
place a point  on . if we choose  as the point at vertical infinity , we can identify the arrangement of pseudo - lines with an arrangement of x - monotone pseudo - lines in the euclidean plane ( where the curves are no longer closed ) .
this requires the application of the levi enlargement lemma to get x - monotonicity , details are given in .
if we sweep this arrangement from left to right , we get again a half - period of a circular sequence , where a change of a pair happens as we sweep across the intersection of two pseudo - lines .
goodman and pollack   show that any circular sequence of a point set describes the topology of an arrangement of pseudo - lines in p2 .
actually , for every point set in the euclidean plane , the standard duality transform for point sets gives an arrangement of straight lines whose crossings , when sweeping from left to right , give a half - period of the circular sequence of the set .
there are , however , arrangements of pseudo - lines in the projective plane that are not stretchable . for them , no point set in the euclidean plane exists that implies any sequence derived from such an arrangements by any choice of . recall that we were able to derive the orientation of a point triple uvw by the position of the points in a half - period of the circular sequence . given a direction around a point at infinity allows us to give a triple of pseudo - lines an orientation , even if there does not exist a corresponding point set order type in the euclidean plane ( i.e. , the sequence is non - realizable ) ; we still get a predicate a that gives each triple an orientation , that is , an abstract order type .
knuth   shows that , for any simple arrangement , a fulfills the five axioms defining cc systems , and from any cc system a corresponding arrangement can be derived ; hence , the terms  cc system  and  abstract order type  are merely synonyms .
we can use either the axioms or a pseudo - line arrangement ( together with a direction around a point at infinity ) for arguing about abstract order types . in the next section
, we will use the model of x - monotone pseudo - lines in the euclidean plane . at first sight , the identification of abstract order types with pseudo - line arrangements in the projective plane might feel like a detour to x - monotone arrangements in the euclidean plane as representation of circular sequences .
this might be the case for the application of the concept in this paper , however , it is profound in the whole theory about abstract order types . recall that different circular sequences might correspond to two point sets having the same order type .
( on the other hand , for arrangements of pseudo - lines in the projective plane , there are transformations that are order - type - preserving and some that are not . )
if two pairs uv and st of four different points change their position in the sequence and uv happens right before st in the half - period , then changing st right before uv results in the same order type .
( to reduce the cases to consider , we will nevertheless make use of that relative position of pseudo - line crossings in the next section .
) there is another aspect that is not directly captured by x - monotone arrangements in the euclidean plane .
when mapping the arrangement from the projective to the euclidean plane , we chose the line at infinity through  arbitrarily ; however , the topology of the arrangement in the projective plane does not depend on the choice of this line .
analogously , the circular sequence of a point set does not depend on the actual starting position of . in terms of pseudo - lines in the euclidean plane , the following can be shown ( more details are given in ) .
consider a crossing of two pseudo - lines that has no further crossings to the left from its initial position .
then we can move this crossing to the right end of the arrangement , such that the resulting arrangement still represents the same abstract order type .
in other words , we  untangle  the crossing at the left end and introduce a new one to the right ( note that this corresponds to removing the position change uv at the beginning by a change vu at the end ) . for every abstract order type and any crossing therein , we can therefore choose a x - monotone representation where that crossing is leftmost .
to see why care has to be taken when we deal with non - realizable order types , note that in general the order type does not capture the relative position of the supporting lines of point pairs and the crossings of these lines .
however , abstract order types capture some of the information that is related to crossings of supporting lines , which allows us to show that the properties needed for basicmin are also present in the abstract setting.5 we use the dual representation of abstract order types in the euclidean plane by x - monotone pseudo - lines ; this allows us to use the obvious meaning of terms like  above  and  below  when describing an arrangement a ( e.g. , a pseudo - line a is above a point b when the point on a that has the same x - coordinate as b has a larger y - coordinate than b ) .
we are given a set s of n elements ( which we call points , even though s might not be a realizable point set ) , containing two special points p and q. the set s is separated by pq into a set u to the right of pq , and a set
l to the left of it ( where  left  and  right  are indicated by a predicate a ) .
we want to obtain the pair l1u1,l1l , u1u that is consecutive on the convex hull of s , where p is to the right of l1u1 .
this is done by obtaining a pair =ljui such that at least half of the points of u ( minus a constant ) are to the right of  and no point of l is to the left of . consider the dual x - monotone pseudo - line arrangement a representing the abstract order type of s. keep in mind that p is an extreme point of the set u{p } , and that r = ur is the median of the points in u ordered radially around p. we can represent the arrangement such that the crossing of the pseudo - lines p and r ( which corresponds to the supporting line of pr in the primal6 ) is the leftmost crossing in the x - monotone representation of a. the linear order of the points around p in the primal splits the set u{ur } into left and right points , separated by pr . in the dual , the right pseudo - lines pass above the crossing pr , and the left pseudo - lines pass below .
the operator  accepts two point pairs , each pair consisting of a left and a right point .
the output of the operator is a pair z consisting of a left and a right point such that all other points are to the right of the oriented line through these points .
this pair z is well - defined in the abstract setting as well ( and there is always a geometric representation due to theorem 1 ) .
recall that we compute a special pair m = m(n22 ) iteratively viam1=s1,m(i+1)=(mi , s(i+1 ) ) .
the crucial property of the pair m = uaub ( and later the line  tangent to ch(l{p , q } ) through ua or ub ) is that at least one endpoint of each pair sim lies on the same side of m as the pivot p. ( we assume that m and the elements of m are directed from the left point to the right point and hence p is to the right of m. ) in the dual , each element of m is represented as the crossing of a right and a left pseudo - line in a ( this corresponds to the supporting line of the matched pair of points in the primal ) .
the crucial property for m in the dual therefore is to have at least one pseudo - line of each pair sim passing below its crossing in a. for realizable point sets , we were able to argue for the correctness of basicmin using the intersection  of a matched pair s with the supporting line of p and r. in the dual , this intersection  corresponds again to a pseudo - line that can be added to a ; this pseudo - line passes through the crossing pr and s. also for non - realizable sets , such a pseudo - line  exists due to the levi enlargement lemma .
in fact , in non - realizable settings the intersections behave in the same transitive manner as in the realizable setting ; see fig . 7 for an illustration of the following statement
. observation 7let 
 z=(a , b ) 
 and 
 z=(c , d ) 
 be two pairs such that the point p is to the right of both pairs ( i.e. , in the dual the pseudo - line p is below the crossings z and 
 z )
. let  (  ) be a dual pseudo - line through the crossings pr and z ( z ) .
if none of a and b is to the left of the primal line 
 z , then the dual pseudo - line 
  
 is above  in the part of the dual arrangement that is to the right of the dual crossing pr .
let 
 z=(a , b ) 
 and 
 z=(c , d ) 
 be two pairs such that the point p is to the right of both pairs ( i.e. , in the dual the pseudo - line p is below the crossings z and 
 z ) .
let  (  ) be a dual pseudo - line through the crossings pr and z ( z ) .
if none of a and b is to the left of the primal line 
 z , then the dual pseudo - line 
  
 is above  in the part of the dual arrangement that is to the right of the dual crossing pr .
hence , after applying basicmin to the matching m , we obtain in the dual a pseudo - line crossing m on a pseudo - line m that passes through the crossing pr , such that no crossing of m is above m .
suppose , for the sake of contradiction , that there is a pair ( a , b ) such that both dual pseudo - lines a and b pass above the crossing m , but the crossing ab is below m . if the crossing ab is to the left of m in the x - monotone arrangement , then , when traversing a from left to right , one would have to pass below m and then go above it again before m. otherwise , if the crossing ab is to the right of m , then b would have to intersect m to be above it at m and then has to be below m again to reach the crossing ab .
both cases contradict the fact that a pair of pseudo - lines intersects exactly once in the x - monotone arrangement .
hence , half of the pseudo - lines are below the pseudo - line crossing m in a. this corresponds to at least half of the points being on the same side of m as p. recall that in the proof of theorem 5 , we chose a directed line  supported by a point ll{q } and either ua or ub such that no elements of l{p , q , ua , ub } is to the left of it .
we now proceed to show that at least one point of each pair ( v , w ) in m is to the right of the directed line  , as demanded in the proof of theorem 5 .
the points involved are { p , q , r , l , ua , ub , v , w } , where l and q might be the same point .
since these are at most eight points , we are allowed to use geometric arguments due to theorem 1 .
however , we must not rely on the positions of the crossing points on the ray pr .
suppose , for the sake of contradiction , that neither of v and w is right of . at least one of v or w has to be to the right of uaub .
these observations imply that vw is an edge of the convex hull of { p , ua , ub , v , w}. however , this means that the crossing of the pseudo - lines v and w is above ua and ub in a , which contradicts the fact that uaub is m. thus , we conclude theorem 8theorem 5 
 also holds for non - realizable cc systems , i.e. , abstract order types .
theorem 5 
 also holds for non - realizable cc systems , i.e. , abstract order types .
we presented two algorithms that only use the information whether a point triple is oriented clockwise or counterclockwise .
both , a halving edge through a given point and a convex hull edge crossing a specified ray , can be found in linear time , without being given the coordinate representation .
we showed that the algorithms also work for general cc systems ( i.e. , abstract order types ) , and thus answer a long - standing open problem of knuth   in the affirmative .
note that the parts of the so - called ultimate convex hull algorithm by kirkpatrick and seidel   that depend on coordinates are essentially the one that find the convex hull edge on the ray that separates a subproblem into two parts .
also , chans output - sensitive algorithm   can be implemented in our setting using theorem 5 .
both allow to improve the time bound given in   for realizable point sets regarding output - sensitivity to o(nlogh ) for h extreme points .
 many properties of finite point sets only depend on the relative position of the points , e.g. , on the order type of the set . however , many fundamental algorithms in computational geometry rely on coordinate representations . 
 this includes the straightforward algorithms for finding a halving line for a given planar point set , as well as finding a point on the convex hull , both in linear time . in his monograph axioms and hulls 
 , knuth asks whether these problems can be solved in linear time in a more abstract setting , given only the orientation of each point triple , i.e. , the sets chirotope , as a source of information . 
 we answer this question in the affirmative . 
 more precisely , we can find a halving line through any given point , as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time . 
 we first give a proof for sets realizable in the euclidean plane and then extend the result to non - realizable abstract order types . 
Introduction
Computing a halving edge in linear time
Computing a convex hull edge in linear time
Realizable point sets
Non-realizable sets
A general proof of the time bound
Conclusion