{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/113010"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/113010","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"On the search for geometric orders, centers, and separation","abstract":"Made available in DSpace on 2022-01-12T21:45:32Z (GMT). No. of bitstreams: 3 JONES-DISSERTATION-2021.pdf: 1914890 bytes, checksum: 366dcc38c4c71d40866af435a7013829 (MD5) LICENSE.txt: 4211 bytes, checksum: e50fd91468e7c0c29de29137ca817c8f (MD5) PROQUEST_LICENSE.txt: 4557 bytes, checksum: b7d874722caa5109ed0d28a53c90906a (MD5) Previous issue date: 2021-07-12","abstract_html":"Made available in DSpace on 2022-01-12T21:45:32Z (GMT). No. of bitstreams: 3 JONES-DISSERTATION-2021.pdf: 1914890 bytes, checksum: 366dcc38c4c71d40866af435a7013829 (MD5) LICENSE.txt: 4211 bytes, checksum: e50fd91468e7c0c29de29137ca817c8f (MD5) PROQUEST_LICENSE.txt: 4557 bytes, checksum: b7d874722caa5109ed0d28a53c90906a (MD5) Previous issue date: 2021-07-12","abstract_has_math":false,"creators":["Jones, Mitchell Francis"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Har-Peled, Sariel","Chan, Timothy","Chekuri, Chandra","Varadarajan, Kasturi"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-01-12T21:45:32Z","date_published":"2022-01-12T21:45:32Z","updated_at":"2026-07-22T22:24:52Z","subjects":["theoretical computer science","computational geometry","approximation algorithms","randomized algorithms","centerpoint","order","separation","yolk","active learning"],"languages":["en"],"rights":["Copyright 2021 Mitchell Jones"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/113010","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Har-Peled, Sariel","Chan, Timothy","Chekuri, Chandra","Varadarajan, Kasturi"]},{"key":"dc:creator","label":"Author","values":["Jones, Mitchell Francis"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-01-12T21:45:32Z","2021-07-12","2021-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["theoretical computer science","computational geometry","approximation algorithms","randomized algorithms","centerpoint","order","separation","yolk","active learning"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Mitchell Jones"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/113010"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Made available in DSpace on 2022-01-12T21:45:32Z (GMT). No. of bitstreams: 3 JONES-DISSERTATION-2021.pdf: 1914890 bytes, checksum: 366dcc38c4c71d40866af435a7013829 (MD5) LICENSE.txt: 4211 bytes, checksum: e50fd91468e7c0c29de29137ca817c8f (MD5) PROQUEST_LICENSE.txt: 4557 bytes, checksum: b7d874722caa5109ed0d28a53c90906a (MD5) Previous issue date: 2021-07-12","\"Over the previous decade, there has been an explosion in the amount of data that needs to be stored, processed, and queried efficiently. Arguably, this is due to the large improvements in data collection methods and machine learning algorithms. A large portion of the data is naturally geometric, consisting of point sets or other simple geometric objects. Examples of operations one may want to perform on finite point sets include ordering the points for storage, sorting, and searching, computing statistical summaries of the points, or breaking the points into smaller clusters for further processing. In this thesis, we study many of the aforementioned problems from a theoretical perspective. In part one we develop a new technique called locality-sensitive orderings. Given a finite point set P in [0,1)^d, we describe a collection of orderings (embeddings of P onto an interval on the real line) which have the property that for any two points in p, q in [0, 1)^d, there is an ordering in which all points between p and q according to the ordering are \"\"close\"\" to either p or q in the original space. Locality-sensitive orderings leads to surprisingly simple data structures for a variety of low dimensional proximity based problems in computational geometry. In the second part of this thesis, we examine various ways to define the center of a point set, and develop efficient algorithms for computing these centers in the process. We develop a new randomized algorithm for computing the approximate centerpoint of a point set. Next, we develop new exact algorithms for finding the yolk of a point set, whose motivation and definition rises from ideas in voting theory. We explore the connection between centerpoints and weak eps-nets by presenting some new alternatives to weak eps-nets. In the third part, we investigate the notion of separation in computational geometry. In particular, we develop a new approximation algorithm for computing the minimum number of lines needed to separate all pairs of a given planar point set. Afterwards, we study the problem of active-learning a concept class which is a convex body. We develop new learning algorithms which assume the computational model has access to an efficient separation oracle for the given convex body.\"","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms","The student, Mitchell Jones, accepted the attached license on 2021-07-09 at 16:21.","The student, Mitchell Jones, submitted this Dissertation for approval on 2021-07-09 at 16:42.","This Dissertation was approved for publication on 2021-07-12 at 09:21.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16840 on 2022-01-12 at 12:44:46"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["On the search for geometric orders, centers, and separation"]}]}],"canonical_facts":{"dc:contributor":["Har-Peled, Sariel","Chan, Timothy","Chekuri, Chandra","Varadarajan, Kasturi"],"dc:creator":["Jones, Mitchell Francis"],"dc:date":["2022-01-12T21:45:32Z","2021-07-12","2021-08"],"dc:description":["Made available in DSpace on 2022-01-12T21:45:32Z (GMT). No. of bitstreams: 3 JONES-DISSERTATION-2021.pdf: 1914890 bytes, checksum: 366dcc38c4c71d40866af435a7013829 (MD5) LICENSE.txt: 4211 bytes, checksum: e50fd91468e7c0c29de29137ca817c8f (MD5) PROQUEST_LICENSE.txt: 4557 bytes, checksum: b7d874722caa5109ed0d28a53c90906a (MD5) Previous issue date: 2021-07-12","\"Over the previous decade, there has been an explosion in the amount of data that needs to be stored, processed, and queried efficiently. Arguably, this is due to the large improvements in data collection methods and machine learning algorithms. A large portion of the data is naturally geometric, consisting of point sets or other simple geometric objects. Examples of operations one may want to perform on finite point sets include ordering the points for storage, sorting, and searching, computing statistical summaries of the points, or breaking the points into smaller clusters for further processing. In this thesis, we study many of the aforementioned problems from a theoretical perspective. In part one we develop a new technique called locality-sensitive orderings. Given a finite point set P in [0,1)^d, we describe a collection of orderings (embeddings of P onto an interval on the real line) which have the property that for any two points in p, q in [0, 1)^d, there is an ordering in which all points between p and q according to the ordering are \"\"close\"\" to either p or q in the original space. Locality-sensitive orderings leads to surprisingly simple data structures for a variety of low dimensional proximity based problems in computational geometry. In the second part of this thesis, we examine various ways to define the center of a point set, and develop efficient algorithms for computing these centers in the process. We develop a new randomized algorithm for computing the approximate centerpoint of a point set. Next, we develop new exact algorithms for finding the yolk of a point set, whose motivation and definition rises from ideas in voting theory. We explore the connection between centerpoints and weak eps-nets by presenting some new alternatives to weak eps-nets. In the third part, we investigate the notion of separation in computational geometry. In particular, we develop a new approximation algorithm for computing the minimum number of lines needed to separate all pairs of a given planar point set. Afterwards, we study the problem of active-learning a concept class which is a convex body. We develop new learning algorithms which assume the computational model has access to an efficient separation oracle for the given convex body.\"","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms","The student, Mitchell Jones, accepted the attached license on 2021-07-09 at 16:21.","The student, Mitchell Jones, submitted this Dissertation for approval on 2021-07-09 at 16:42.","This Dissertation was approved for publication on 2021-07-12 at 09:21.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16840 on 2022-01-12 at 12:44:46"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/113010"],"dc:language":["en"],"dc:rights":["Copyright 2021 Mitchell Jones"],"dc:subject":["theoretical computer science","computational geometry","approximation algorithms","randomized algorithms","centerpoint","order","separation","yolk","active learning"],"dc:title":["On the search for geometric orders, centers, and separation"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:52Z"}