This seems to be a specific application of alpha shapes, which are from my reading a more general form of this problem. R has the alphahull module, which has excellent documentation on computing alpha shapes. Also check this detailed background on alpha shapes. If you only want to compute convex/concave hulls, check out lasboundary, part of lastools, it scales well and can handle millions of input points.

Finally, this interesting application of alpha shapes by Flickr made the rounds a while ago, showing their utility for aggregating user generated point content:

Here is what you are looking for.

You can download and test the program: (in java, under GPL license)

The paper presenting the algorithm is there:

Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008) Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition v41, 3224-3236

JTS (https://github.com/locationtech/jts) provides a Convex Hull implementation. Martin Davies also mentioned having an Alpha Shape algorithm in the works so you might want to check the SVN repository to see if it is in yet if that's what you want.

About R implementation Alpha-Shapes, there's an article about "Converting Alpha-Shapes into SP Objects"

It's based on alphahull, sp and spgrass6 http://casoilresource.lawr.ucdavis.edu/drupal/node/919

Speaking about JTS, you can use Geoscript for manipulating JTS library. http://geoscriptblog.blogspot.com/2010/06/unwrapped-jts-with-python.html for an article about convex hull. GeoScript implementations are available in JavaScript, Python, Scala, and Groovy. The official website : http://geoscript.org

There is an implementation of ST_ConcaveHull in PostGIS trunk. http://postgis.net/docs/ST_ConcaveHull.html

I created a highly-efficient tool, called lasboundary (1,2), that computes a concave hull for LIDAR in LAS/LAZ/SHP/ASCII format and stores the result as a vector boundary polygon in ESRI Shapefile format or a geo-referenced KML file.

Here is an example run:

C:lastoolsbin>lasboundary -i SerpentMound.las -o SerpentMound_boundary.shp
reading 3265110 points and computing convex hull for 3265110 points
growing inward towards concave hull (with concavity = 50)
outputting the concave hull
concave hull has 1639 points

Some result pictures are here.

Here's a program written in C that computes convex hulls, alpha shapes, Delauney triangluations and Voronoi volumes:

• Hull - Ken Clarkson (2002)

Another convex hull algorithm with C and Java implementations is here:

• Convex Hull (2D) - Computational Geometry in C, Joseph O'Rourke (1998)

Here is an R function that implements the Alpha Hull model. The output is an sp polygon object. Please see the example in the header. It requires the sp, alphahull and maptools packages.

**Update (01-15-2018) There have been numerous changes to the resulting objects produced by the alphahull package. As such, I needed to rewrite the function. I added a convexHull function to the spatialEco package. However, due to licensing restrictions in the alphahull package this function is only available in the development version on GitHub. The development version can be installed using:

library(devtools)
install_github("jeffreyevans/spatialEco")

Here is an example of the functions usage

library(sp)
library(spatialEco)
data(meuse)
 coordinates(meuse) = ~x+y
a <- convexHull(meuse, alpha=100000)
  plot(a)
    points(meuse, pch=19)

Convert the resulting SpatialLinesDataFrame to SpatialPolygonsDataFrame

library(sf)
a <- sf::st_as_sf(a) 
a <- sf::st_polygonize(a)
class( a <- as(a, "Spatial") )
  plot(a)

Test multiple alpha values

par(mfcol=c(2,2))
   for (a in c(500, 1500, 5000, 100000)) {
   ch <- convexHull(meuse, alpha = a)
     plot(ch)
      points(meuse, pch=19)
        title( paste0("alpha=", a))      
   }

There is a new Addon for GRASS GIS 7 available: v.concave.hull. See also http://grasswiki.osgeo.org/wiki/Create_concave_hull

To help with the "proper definition" part of your question; you may have looked at https://en.wikipedia.org/wiki/Convex_hull and gotten what could well be considered a "proper" definition, but found it lacking, so perhaps a more "useful" definition is:

For every point inside a convex hull, a straight line to any point not within the hull will only intersect the hull once.

This is useful because given a point you can construct a line through it and test for that constructed line intersecting segments of the hull.

• No intersection the point is not in the hull.
• One intersection the point is on the hull.
• Two intersections the point is within the hull
• A straight line cannot intersect a convex hull more than twice

To add to previous answers for this post, at least as of QGIS 2.6 does have concave hull algorithm

Parameters
Input point layer [vector: point]
put parameter description here

Threshold (0-1, where 1 is equivalent with Convex Hull) [number]
put parameter description here
Default: 0.3

Allow holes [boolean]
put parameter description here
Default: True

Split multipart geometry into singleparts geometries [boolean]
Default: False

Outputs Concave hull [vector]
put output description here

Console usage
processing.runalg('qgis:concavehull', input, alpha, holes, no_multigeometry, output)

Also, Esri has a tool Minimum Bounding Geometry (Data Management)

Which allows you to choose the geometry type, which includes convex hull