Efficient algorithms for beacon routing in polygons

In a paper by Biro et al. [7], a novel twist on guarding in art galleries is introduced. A beacon is a fixed point with an attraction pull that can move points within the polygon. Points move greedily to monotonically decrease their Euclidean distance to the beacon by moving straight towards the beacon or sliding on the edges of the polygon. The beacon attracts a point if the point eventually reaches the beacon. Unlike most variations of the art gallery problem, the beacon attraction has the intriguing property of being asymmetric, leading to separate definitions of attraction region and inverse attraction region. The attraction region of a beacon is the set of points that it attracts. For a given point in the polygon, the inverse attraction region is the set of beacon locations that can attract the point. We first study the characteristics of beacon attraction. We consider the quality of a "successful" beacon attraction and provide an upper bound of $\sqrt{2}$ on the ratio between the length of the beacon trajectory and the length of the geodesic distance in a simple polygon. In addition, we provide an example of a polygon with holes in which this ratio is unbounded. Next we consider the problem of computing the shortest beacon watchtower in a polygonal terrain and present an $O(n \log n)$ time algorithm to solve this problem. In doing this, we introduce $O(n \log n)$ time algorithms to compute the beacon kernel and the inverse beacon kernel in a monotone polygon. We also prove that $\Omega(n \log n)$ time is a lower bound for computing the beacon kernel of a monotone polygon. Finally, we study the inverse attraction region of a point in a simple polygon. We present algorithms to efficiently compute the inverse attraction region of a point for simple, monotone, and terrain polygons with respective time complexities $O(n^2)$, $O(n \log n)$ and $O(n)$. We show that the inverse attraction region of a point in a simple polygon has linear complexity and the problem of computing the inverse attraction region has a lower bound of $\Omega(n \log n)$ in monotone polygons and consequently in simple polygons.

CONSTITUTIONAL JUSTICE IN AFRICA: An Examination of Constitutional Positivism, Fundamental Law and Rights in Ghana and Nigeria

This work explores the idea of constitutional justice in Africa with a focus on constitutional interpretation in Ghana and Nigeria. The objective is to develop a theory of constitutional interpretation based upon a conception of law that allows the existing constitutions of Ghana and Nigeria to be construed by the courts as law in a manner that best serves the collective wellbeing of the people. The project involves an examination of both legal theory and substantive constitutional law. The theoretical argument will be applied to show how a proper understanding of the ideals of the rule of law and constitutionalism in Ghana and Nigeria necessitate the conclusion that socio-economic rights in those countries are constitutionally protected and judicially enforceable. The thesis argues that this conclusion follows from a general claim that constitutions should represent a ‘fundamental law’ and must be construed as an aspirational moral ideal for the common good of the people. The argument is essentially about the inherent character of ‘legality’ or the ‘rule of law.’ It weaves together ideas developed by Lon Fuller, Ronald Dworkin, T.R.S. Allan and David Dyzenhaus, as well as the strand of common law constitutionalism associated with Sir Edward Coke, to develop a moral sense of ‘law’ that transcends the confines of positive or explicit law while remaining inherently ‘legal’ as opposed to purely moral or political. What emerges is an unwritten fundamental law of reason located between pure morality or natural law on the one hand and strict, explicit, or positive law on the other. It is argued that this fundamental law is, or should be, the basis of constitutional interpretation, especially in transitional democracies like Ghana and Nigeria, and that it grounds constitutional protection for socio-economic rights. Equipped with this theory of law, courts in developing African countries like Ghana and Nigeria will be in a better position to contribute towards developing a real sense of constitutional justice for Africa.